1001 Gaussian Prime
http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=3798
.......................................我是真的一言难尽
1002 Sum of Factorials
http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=2696
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 #define N 1000005
5 int a[15];
6 void init()
7 {
8 a[0]=a[1]=1;
9 for(int i=2;i<10;i++)
10 a[i]=a[i-1]*i;
11 }
12 int main()
13 {
14 init();
15 int n;
16 while(~scanf("%d",&n),n>=0)
17 {
18 if(n==0)
19 {
20 printf("NO\n");
21 continue;
22 }
23 int all=0;
24 for(int i=9;i>=0;i--)
25 {
26 all+=a[i];
27 if(all>n) all-=a[i];
28 }
29 if(all==n) printf("YES\n");
30 else printf("NO\n");
31 }
32 }
View Code
1003 Billboard
http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6016
黑板报h*w，第i个广告是1*wi。优先上、左。线段树存剩余最大容量。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 #define M 200005
5 int tre[M<<2];
6 void build(int ind,int left,int right,int w)
7 {
8 tre[ind]=w;
9 if(left==right) return;
10 int mid=(left+right)>>1;
11 build(ind*2,left,mid,w);
12 build(ind*2+1,mid+1,right,w);
13 tre[ind]=max(tre[ind*2],tre[ind*2+1]);
14 }
15 int finda(int ind,int left,int right,int a)
16 {
17 if(left==right)
18 {
19 tre[ind]-=a;
20 return left;
21 }
22 int mid=(left+right)>>1,ans;
23 if(tre[ind*2]>=a) ans=finda(ind*2,left,mid,a);
24 else ans=finda(ind*2+1,mid+1,right,a);
25 tre[ind]=max(tre[ind*2],tre[ind*2+1]);
26 return ans;
27 }
28 int main()
29 {
30 int h,w,n;
31 while(~scanf("%d%d%d",&h,&w,&n))
32 {
33 int minn=min(h,n);
34 build(1,1,minn,w);
35 while(n--)
36 {
37 int a;scanf("%d",&a);
38 if(tre[1]<a) printf("-1\n");
39 else printf("%d\n",finda(1,1,minn,a));
40 }
41 }
42 }
View Code
1004 Monkey Party
http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6054
咕
1005 Happy Necklace
http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6064
一点都不happy的项链，f(2)=3, f(3)=4, f(4)=6, f(n)=f(n-1)+f(n-2)，矩阵快速幂。
1 1 0
A = 0 0 1
1 0 0
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int mod=1e9+7;
5 struct p{
6 ll rol,col;
7 ll matris[3][3];
8 };
9 p Matris(p a,p b)
10 {
11 p tem;
12 memset(tem.matris,0,sizeof(tem.matris));
13 for(ll i=0;i<3;i++)
14 for(ll j=0;j<3;j++)
15 for(ll k=0;k<3;k++)
16 {
17 tem.matris[i][j]+=a.matris[i][k]*(b.matris[k][j]%mod);
18 tem.matris[i][j]%=mod;
19 }
20 return tem;
21 }
22 ll quick_mi(ll n)
23 {
24 p res,tep;
25 res.matris[0][0]=6,res.matris[0][1]=4,res.matris[0][2]=3;
26 for(int i=1;i<=2;i++)
27 for(int j=0;j<=2;j++)
28 res.matris[i][j]=0;
29 tep.matris[0][0]=1,tep.matris[0][1]=1,tep.matris[0][2]=0;
30 tep.matris[1][0]=0,tep.matris[1][1]=0,tep.matris[1][2]=1;
31 tep.matris[2][0]=1,tep.matris[2][1]=0,tep.matris[2][2]=0;
32 while(n)
33 {
34 if(n&1) res=Matris(res,tep);
35 tep=Matris(tep,tep);
36 n/=2;
37 }
38 return res.matris[0][0]%mod;
39 }
40 int main()
41 {
42 int t;scanf("%d",&t);
43 while(t--)
44 {
45 ll n;scanf("%lld",&n);
46 if(n==2) printf("3\n");
47 else if(n==3) printf("4\n");
48 else if(n==4) printf("6\n");
49 else printf("%lld\n",quick_mi(n-4));
50 }
51 }
View Code
1006 CA Loves GCD
http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6068
我不爱
1007 Squarefree number
http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6071
欧拉筛把10^6内的素数标下，如果除了两个或以上就No。素数除完了可能还很大，就要看是不是完全平方数，否则n就是一个很大的素数或者两个大于10^6的素数乘积。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 #define N 1000005
5 int prim[N+5];
6 int vis[N+5],cnt=0;
7 void init()
8 {
9 vis[0]=vis[1]=1;
10 for(int i=0;i<N;i++)
11 if(!vis[i])
12 {
13 prim[cnt++]=i;
14 for(ll j=(ll)i*i;j<N;j+=i) vis[j]=1;
15 }
16 }
17 int main()
18 {
19 init();
20 int t;scanf("%d",&t);
21 for(int kk=1;kk<=t;kk++)
22 {
23 int flag=1;
24 ll n;scanf("%lld",&n);
25 for(int i=0;i<cnt;i++)
26 {
27 if(n%prim[i]==0)
28 {
29 int num=0;
30 while(n%prim[i]==0) n/=prim[i],num++;
31 if(num>=2)
32 {
33 flag=0;
34 printf("Case %d: No\n",kk);
35 break;
36 }
37 }
38 }
39 if(n>1000000&&flag)
40 {
41 int q=(int)sqrt(n);
42 if((ll)q*q==n) printf("Case %d: No\n",kk);
43 else printf("Case %d: Yes\n",kk);
44 continue;
45 }
46 if(flag) printf("Case %d: Yes\n",kk);
47 }
48 }
View Code
1008 Gym Class
http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6081
选自己前面包括自己的最小id作为评分，记录一下要加上的评分minn。没有要求的入度为0进队列。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int MAXN=1e9;
5 const int N=100005;
6 vector<int> vec[N];
7 int inde[N];
8 priority_queue<int> q;
9 void init()
10 {
11 memset(inde,0,sizeof(inde));
12 for(int i=1;i<=N;i++) vec[i].clear();
13 while(!q.empty()) q.pop();
14 }
15 int main()
16 {
17 int t;scanf("%d",&t);
18 while(t--)
19 {
20 ll ans=0,minn=MAXN;
21 init();
22 int n,m;scanf("%d%d",&n,&m);
23 while(m--)
24 {
25 int a,b;scanf("%d%d",&a,&b);
26 inde[b]++;
27 vec[a].push_back(b);
28 }
29 for(int i=1;i<=n;i++)
30 if(!inde[i]) q.push(i);
31 while(!q.empty())
32 {
33 ll p=q.top();q.pop();
34 minn=min(p,minn);
35 ans+=minn;
36 for(int i=0;i<vec[p].size();i++)
37 {
38 inde[vec[p][i]]--;
39 if(inde[vec[p][i]]==0) q.push(vec[p][i]);
40 }
41 }
42 printf("%lld\n",ans);
43 }
44 }
View Code