2019/11/02 TZOJ

1001 ShaoLin

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6003

标记一下id=1的，lower_bound找到在当前q前后的能力(now=*it,ex=*(--it))

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 map<int,int> ma;
 5 set<int> se;
 6 int main()
 7 {
 8     int t;
 9     while(~scanf("%d",&t),t)
10     {
11         ma.clear(),se.clear();
12         ma[1000000000]=1;
13         se.insert(1000000000);
14         while(t--)
15         {
16             int id,q;scanf("%d%d",&id,&q);
17             ma[q]=id;
18             set<int> ::iterator it=se.lower_bound(q);
19             if(it==se.end())
20                 printf("%d %d
",id,ma[*(--it)]);
21             else{
22                 if(it!=se.begin())
23                 {
24                     int now=*it,ex=*(--it);
25                     if((now-q)>=(q-ex)) printf("%d %d
",id,ma[ex]);
26                     else printf("%d %d
",id,ma[now]);
27                 }
28                 else printf("%d %d
",id,ma[*it]);
29             }
30             se.insert(q);
31         }
32     }
33 }

View Code

1002 Find the Numbers

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=3988

emm暴力了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int a[105],cnt=0;
 5 int main()
 6 {
 7     int s,p,k;scanf("%d%d%d",&s,&p,&k);
 8     for(int i=1;i<=p/2;i++)
 9         if(p%i==0) a[cnt++]=i;
10     a[cnt]=p;
11     if(k==1) printf("%s
",s>=p?"YES":"NO");
12     else if(k==2)
13     {
14         for(int i=0;i<=cnt;i++)
15             for(int j=0;j<=cnt;j++)
16                 if(a[i]*a[j]==p&&(a[i]+a[j])==s)
17                 {
18                     printf("YES
");
19                     return 0;
20                 }
21         printf("NO
");
22     }
23     else if(k==3)
24     {
25         for(int i=0;i<=cnt;i++)
26             for(int j=0;j<=cnt;j++)
27                 for(int k=0;k<=cnt;k++)
28                     if(a[i]*a[j]*a[k]==p&&(a[i]+a[j]+a[k])==s)
29                     {
30                         printf("YES
");
31                         return 0;
32                     }
33         printf("NO
");
34     }
35     else if(k==4)
36     {
37         for(int i=0;i<=cnt;i++)
38             for(int j=0;j<=cnt;j++)
39                 for(int k=0;k<=cnt;k++)
40                     for(int l=0;l<=cnt;l++)
41                         if(a[i]*a[j]*a[k]*a[l]==p&&(a[i]+a[j]+a[k]+a[l])==s)
42                         {
43                             printf("YES
");
44                             return 0;
45                         }
46         printf("NO
");
47     }
48 }

View Code

1003 Mobile phones

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6017

输入1在(x,y)点加上a，输入2是查询(x1,y1)到(x2,y2)矩阵的元素和。贴一下参考的连接https://blog.csdn.net/baymax520/article/details/81276368

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=1025;
 5 int ma[N][N],n,m;
 6 int lowbit(int x){return x&-x;}
 7 void add(int x,int y,int num)
 8 {
 9     for(int i=x;i<=m;i+=lowbit(i))
10         for(int j=y;j<=m;j+=lowbit(j))ma[i][j]+=num;
11 }
12 void query(int x1,int y1,int x2,int y2)
13 {
14     int ans=0;
15     for(int i=x2;i>0;i-=lowbit(i))
16         for(int j=y2;j>0;j-=lowbit(j))ans+=ma[i][j];
17     for(int i=x2;i>0;i-=lowbit(i))
18         for(int j=y1-1;j>0;j-=lowbit(j))ans-=ma[i][j];
19     for(int i=x1-1;i>0;i-=lowbit(i))
20         for(int j=y2;j>0;j-=lowbit(j))ans-=ma[i][j];
21     for(int i=x1-1;i>0;i-=lowbit(i))
22         for(int j=y1-1;j>0;j-=lowbit(j))ans+=ma[i][j];
23     printf("%d
",ans);
24 }
25 int main()
26 {
27     while(~scanf("%d",&n))
28     {
29         if(n==0){
30             scanf("%d",&m);
31             memset(ma,0,sizeof(ma));
32         }
33         else if(n==1){
34             int x,y,a;scanf("%d%d%d",&x,&y,&a);
35             add(++x,++y,a);
36         }
37         else if(n==2){
38             int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
39             query(++x1,++y1,++x2,++y2);
40         }
41         else if(n==3) break;
42     }
43 }

View Code

1004 Fair Division

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=3386

排个序，钱少的在前边，钱一样多的就按id从大到小排。每个人都付剩余sum/(n-i)的平均钱。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 struct p{
 5     int pay,val,id;
 6 }kk[105];
 7 bool cmp(p a,p b)
 8 {
 9     if(a.val!=b.val) return a.val<b.val;
10     return a.id>b.id;
11 }
12 bool un_cmp(p a,p b)
13 {
14     return a.id<b.id;
15 }
16 int main()
17 {
18     int t;
19     for(scanf("%d",&t);t;t--)
20     {
21         int sum,n,all=0;scanf("%d%d",&sum,&n);
22         for(int i=0;i<n;i++)
23         {
24             scanf("%d",&kk[i].val);
25             kk[i].id=i;
26             all+=kk[i].val;
27         }
28         if(all<sum)
29         {
30             printf("IMPOSSIBLE
");
31             continue;
32         }
33         sort(kk,kk+n,cmp);
34         for(int i=0;i<n;i++)
35         {
36             kk[i].pay=min(kk[i].val,sum/(n-i));
37             sum-=kk[i].pay;
38         }
39         sort(kk,kk+n,un_cmp);
40         for(int i=0;i<n;i++) printf("%d%c",kk[i].pay,i==n-1?'
':' ');
41     }
42 }

View Code

1005 Anniversary party

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6060

遍历一遍找到根节点，树形dp

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int dp[6005][2],t;
 5 int father[6005];
 6 int vis[6005];
 7 void solve(int node)
 8 {
 9     vis[node]=1;
10     for(int i=1;i<=t;i++)
11     {
12         if(!vis[i]&&father[i]==node)
13         {
14             solve(i);
15             dp[node][1]+=dp[i][0];
16             dp[node][0]+=max(dp[i][0],dp[i][1]);
17         }
18     }
19 }
20 void init()
21 {
22     memset(dp,0,sizeof(dp));
23     memset(vis,0,sizeof(vis));
24     memset(father,0,sizeof(father));
25 }
26 int main()
27 {
28     while(~scanf("%d",&t))
29     {
30         init();
31         int l,k,root;
32         for(int i=1;i<=t;i++) scanf("%d",&dp[i][1]);
33         while(~scanf("%d%d",&l,&k),l||k) father[l]=k;
34         for(int i=1;i<=t;i++)
35             if(!father[i]) root=i;
36         solve(root);
37         printf("%d
",max(dp[root][1],dp[root][0]));
38     }
39 }

View Code

1006 Twin Prime Conjecture

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=6070

问的是n大的数里面有多少个前后素数相差2的twin素数。只有10^5，不大。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define N 100005
 5 int ans[N];
 6 int prime[N];
 7 int vis[N];
 8 const int n=100000;
 9 int  cnt=0,now=0;
10 void init()
11 {
12     for(int i=2;i<=n;i++)
13     {
14         ans[i]=now;
15         if(vis[i]==0)
16         {
17             prime[cnt]=i;
18             if(cnt!=0&&prime[cnt]-prime[cnt-1]==2) now++;
19             ans[i]=now;
20             cnt++;
21         }
22         for(int j=0;j<cnt&&i*prime[j]<=n;j++)
23         {
24             vis[i*prime[j]]=true;
25             if(i%prime[j]==0) break;
26         }
27     }
28 }
29 int main()
30 {
31     init();
32     //for(int i=0;i<20;i++) printf("%d
",ans[i]);
33     int n;
34     while(~scanf("%d",&n),n>=0)
35     {
36         printf("%d
",ans[n]);
37     }
38 }

View Code

//1007跑了

1008 Manhattan Sort

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=3677

把排序后和排序前的位置相差的和除以二

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 struct p{
 5     int numb,id;
 6 }a[35];
 7 bool cmp(p x,p y)
 8 {
 9     return x.numb<y.numb;
10 }
11 map<int,int> b;
12 int main()
13 {
14     int t;scanf("%d",&t);
15     for(int kk=1;kk<=t;kk++)
16     {
17         int n;scanf("%d",&n);
18         for(int i=1;i<=n;i++) scanf("%d",&a[i].numb),a[i].id=b[a[i].numb]=i;
19         sort(a+1,a+n+1,cmp);
20         int ans=0;
21         for(int i=1;i<=n;i++)
22             ans+=abs(i-b[a[i].numb]);
23         printf("Case #%d: %d
",kk,ans/2);
24     }
25 }

View Code

1009 SPF

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=2018

割点，困了，再说。