我还只能化简到这个程度：uint F(int n){
uint r=0;
for(int i=2;i<=n;++i){
r+=n/i;
}
return r;
}
O(n)时间复杂度显然是不够的——所以如你所料，我还没做出来。
Sunday, 22 March 2009
The 9th Zhejiang University Programming Contest B
题目在这里：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=3207
The 9th Zhejiang University Programming Contest I
题目在这里：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=3214
#include <iostream>
using namespace std;
unsigned int gray2dec(unsigned int x) {
unsigned int y = x; while(x>>=1) y ^= x; return y;
}
int main() {
int N,n;
for(cin>>N;N;--N){
cin>>n; cout<<gray2dec((1<<n)-1)<<endl;
}
return 0;
}
The 9th Zhejiang University Programming Contest F
题目在这里 http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=3211
#include <iostream>
#include <memory.h>
using namespace std;
typedef unsigned int uint;
int p10(int n){
switch(n){
case 0: return 1;
case 1: return 10;
case 2: return 100;
case 3: return 1000;
case 4: return 10000;
case 5: return 100000;
case 6: return 1000000;
}
}
bool fail(int n){
for(;n;--n)
cin.ignore(8,'\n');
return false;
}
bool check(uint n){
char tmp[8];
bool should_move[6]={false};
int i,remained;
cin.getline(tmp,8);
for(i=0;i<6;++i)
should_move[i]=(n/p10(i))%10>=5;
for(i=0;i<6;++i)
if((tmp[i]=='o')==should_move[5-i]) return fail(7);
cin.getline(tmp,8);
cin.getline(tmp,8); //---
cin.getline(tmp,8);
cin.getline(tmp,8);
for(i=0;i<6;++i)
should_move[i]=(n/p10(i))%10%5==1;
for(i=0;i<6;++i)
if((tmp[i]=='o')==should_move[5-i]) return fail(3);
cin.getline(tmp,8);
for(i=0;i<6;++i)
should_move[i]=(n/p10(i))%10%5==2;
for(i=0;i<6;++i)
if((tmp[i]=='o')==should_move[5-i]) return fail(2);
cin.getline(tmp,8);
for(i=0;i<6;++i)
should_move[i]=(n/p10(i))%10%5==3;
for(i=0;i<6;++i)
if((tmp[i]=='o')==should_move[5-i]) return fail(1);
cin.getline(tmp,8);
for(i=0;i<6;++i)
should_move[i]=(n/p10(i))%10%5==4;
for(i=0;i<6;++i)
if((tmp[i]=='o')==should_move[5-i]) return false;
return true;
}
int main() {
int N,a,b;
for(cin>>N;N;--N) {
cin>>a>>b; cin.get();
cout<<(check((a+b)*(b-a+1)/2)?"No mistake":"Mistake")<<endl;
}
return 0;
}
The 9th Zhejiang University Programming Contest A
题目如下：
The 9th Zhejiang University Programming Contest - A
Square Root Day
Time Limit: 1 Second Memory Limit: 32768 KB
Square Root Day is an unofficial holiday celebrated on days when both the day of
the month and the month are the square root of either the last two or three
digits of the year. For example, the last Square Root Day was March 3, 2009
(3/3/09), and the next Square Root Day will be April 4, 2016 (4/4/16).
Input
The first line of the input contains an integer T (T <= 10), indicating the
number of cases.
Then T lines follows, each has two integers x and y (1 <= x <= y <= 2009).
Output
Output the number of Square Root Days from year x to year y, both inclusive.
Sample Input
2
2009 2009
81 100
Sample Output
1
2
#include <iostream>
#include <cmath>
using namespace std;
int calc(int from,int to){
int n=0;
for(;from<=to;++from) {
int x3=from%1000,x2=from%100;
if(x3==144) ++n;
if(x3==121) ++n;
if(x3==100) ++n;
if(x2==81) ++n;
if(x2==64) ++n;
if(x2==49) ++n;
if(x2==36) ++n;
if(x2==25) ++n;
if(x2==16) ++n;
if(x2==9) ++n;
if(x2==4) ++n;
if(x2==1) ++n;
}
return n;
}
int main() {
int n,f,t;
for(cin>>n;n&&cin>>f>>t;--n)
cout<<calc(f,t)<<endl;
return 0;
}
Saturday, 21 March 2009
POJ ( acm.pku.edu.cn ) 3673
#include <iostream>
using namespace std;
unsigned __int64 mul(char* a,char*b){
unsigned __int64 r=0;
for(;*a;++a) {
if(*a=='0')continue;
for(char* c=b;*c;++c) {
r+=(*a-'0')*(*c-'0');
}
}
return r;
}
int main()
{
for(char a[16],b[16];cin>>a>>b;cout<<mul(a,b)<<endl);
return 0;
}
POJ ( acm.pku.edu.cn ) 3650
我爱STL
#include <iostream>
#include <string>
using namespace std;
#define CR(c,n) case c: str.replace(b,1,"%" #n); b+=2; break
string replace_all(string& str){
size_t b;
for(b=0;b<str.length();++b) {
switch ( str[b] ){
CR(' ',20);CR('!',21);CR('$',24);CR('%',25);
CR('(',28);CR(')',29);CR('*',2a);
default:break;
}
}
return str;
}
int main()
{
for(string str; getline(cin,str)&&str!="#"; cout<<replace_all(str)<<endl);
return 0;
}
POJ ( acm.pku.edu.cn ) 3589
水啊水啊
#include <iostream>
using namespace std;
int main() {
int N;
for(cin>>N;N;--N){
int digit[10]={0},A=0,B=0;
char x[5],y[5],*i,*j;
cin>>x>>y;
for(i=x,j=y;*i;++digit[*i-'0'],++i,++j) if(*i==*j) ++A;
for(i=x,j=y;*i;++i,++j) if(digit[*j-'0']&&*i!=*j) ++B;
cout<<A<<'A'<<B<<'B'<<endl;
}
return 0;
}
POJ ( acm.pku.edu.cn ) 3518
我挺自我欣赏那二分查找的算法
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
typedef unsigned int uint;
uint primes[100001];
struct init {
init() {
primes[0]=2;
bool ok=true;
int n=1;
uint p;
for (uint i=3;n<=100000;i+=2) {
ok=true;
uint sq=sqrt(double(i))+1;
for (uint j=1;j<n;++j) {
p=primes[j];
if (p>sq) {
ok=true;
break;
}
if (i%p==0) {
ok=false;
break;
}
}
if (ok) {
primes[n]=i;
++n;
}
}
}
}initer;
template <class T>
size_t bin_search(T* array, size_t len, T const& n) {
size_t a=0,b=len,m1,m2=-1;
for (m1=(a+b)>>1;m1!=m2;) {
m2=m1;
if (array[m1]==n) return m1;
else if (array[m1]<n) a=m1;
else /*(array[m1]>n)*/b=m1;
m1=(a+b)>>1;
}
if (array[m1]<n) return m1;
else /*(array[m1]>n)*/ return m1-1;
}
int main() {
for(int n;cin>>n&&n;){
int p=bin_search<uint>(primes,100000,n);
if (primes[p]==n) cout<<0<<endl;
else cout<<primes[p+1]-primes[p]<<endl;
}
return 0;
}
POJ ( acm.pku.edu.cn ) 3100
本以为用 floor(pow(b,1./n)) 可以直接算出来——谁知道错了。
#include <iostream>
#include <cmath>
using namespace std;
inline int p(int a,int b){
for(int x=a;--b>0;a*=x);
return a;
}
int main() {
for(int b,n,i;cin>>b>>n&&b&&n;cout<<endl){
double x=floor(pow(b,1./n));
for(i=x;p(i,n)<b;++i);
if(p(i,n)-b>b-p(i-1,n))
cout<<i-1;
else
cout<<i;
}
return 0;
}
POJ ( acm.pku.edu.cn ) 3094
我爱水题我爱水题
#include <iostream>
#include <string>
using namespace std;
int main(){
for(string str;getline(cin,str)&&str!="#";){
int crc=0;
for(int i=0;i<str.length();++i){
char c=str[i];
if(c<='Z'&&c>='A')
crc+=(i+1)*(c-'A'+1);
}
cout<<crc<<endl;
}
return 0;
}
Subscribe to:
Posts (Atom)
