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))

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 map<int,int> ma;

 set<int> se;

 int main()

 {

     int t;

     while(~scanf("%d",&t),t)

     {

         ma.clear(),se.clear();

         ma[]=;

         se.insert();

         while(t--)

         {

             int id,q;scanf("%d%d",&id,&q);

             ma[q]=id;

             set<int> ::iterator it=se.lower_bound(q);

             if(it==se.end())

                 printf("%d %d\n",id,ma[*(--it)]);

             else{

                 if(it!=se.begin())

                 {

                     int now=*it,ex=*(--it);

                     if((now-q)>=(q-ex)) printf("%d %d\n",id,ma[ex]);

                     else printf("%d %d\n",id,ma[now]);

                 }

                 else printf("%d %d\n",id,ma[*it]);

             }

             se.insert(q);

         }

     }

 }

1002 Find the Numbers

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

emm暴力了

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int a[],cnt=;

 int main()

 {

     int s,p,k;scanf("%d%d%d",&s,&p,&k);

     for(int i=;i<=p/;i++)

         if(p%i==) a[cnt++]=i;

     a[cnt]=p;

     if(k==) printf("%s\n",s>=p?"YES":"NO");

     else if(k==)

     {

         for(int i=;i<=cnt;i++)

             for(int j=;j<=cnt;j++)

                 if(a[i]*a[j]==p&&(a[i]+a[j])==s)

                 {

                     printf("YES\n");

                     return ;

                 }

         printf("NO\n");

     }

     else if(k==)

     {

         for(int i=;i<=cnt;i++)

             for(int j=;j<=cnt;j++)

                 for(int k=;k<=cnt;k++)

                     if(a[i]*a[j]*a[k]==p&&(a[i]+a[j]+a[k])==s)

                     {

                         printf("YES\n");

                         return ;

                     }

         printf("NO\n");

     }

     else if(k==)

     {

         for(int i=;i<=cnt;i++)

             for(int j=;j<=cnt;j++)

                 for(int k=;k<=cnt;k++)

                     for(int l=;l<=cnt;l++)

                         if(a[i]*a[j]*a[k]*a[l]==p&&(a[i]+a[j]+a[k]+a[l])==s)

                         {

                             printf("YES\n");

                             return ;

                         }

         printf("NO\n");

     }

 }

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

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=;

 int ma[N][N],n,m;

 int lowbit(int x){return x&-x;}

 void add(int x,int y,int num)

 {

     for(int i=x;i<=m;i+=lowbit(i))

         for(int j=y;j<=m;j+=lowbit(j))ma[i][j]+=num;

 }

 void query(int x1,int y1,int x2,int y2)

 {

     int ans=;

     for(int i=x2;i>;i-=lowbit(i))

         for(int j=y2;j>;j-=lowbit(j))ans+=ma[i][j];

     for(int i=x2;i>;i-=lowbit(i))

         for(int j=y1-;j>;j-=lowbit(j))ans-=ma[i][j];

     for(int i=x1-;i>;i-=lowbit(i))

         for(int j=y2;j>;j-=lowbit(j))ans-=ma[i][j];

     for(int i=x1-;i>;i-=lowbit(i))

         for(int j=y1-;j>;j-=lowbit(j))ans+=ma[i][j];

     printf("%d\n",ans);

 }

 int main()

 {

     while(~scanf("%d",&n))

     {

         if(n==){

             scanf("%d",&m);

             memset(ma,,sizeof(ma));

         }

         else if(n==){

             int x,y,a;scanf("%d%d%d",&x,&y,&a);

             add(++x,++y,a);

         }

         else if(n==){

             int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

             query(++x1,++y1,++x2,++y2);

         }

         else if(n==) break;

     }

 }

1004 Fair Division

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

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

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 struct p{

     int pay,val,id;

 }kk[];

 bool cmp(p a,p b)

 {

     if(a.val!=b.val) return a.val<b.val;

     return a.id>b.id;

 }

 bool un_cmp(p a,p b)

 {

     return a.id<b.id;

 }

 int main()

 {

     int t;

     for(scanf("%d",&t);t;t--)

     {

         int sum,n,all=;scanf("%d%d",&sum,&n);

         for(int i=;i<n;i++)

         {

             scanf("%d",&kk[i].val);

             kk[i].id=i;

             all+=kk[i].val;

         }

         if(all<sum)

         {

             printf("IMPOSSIBLE\n");

             continue;

         }

         sort(kk,kk+n,cmp);

         for(int i=;i<n;i++)

         {

             kk[i].pay=min(kk[i].val,sum/(n-i));

             sum-=kk[i].pay;

         }

         sort(kk,kk+n,un_cmp);

         for(int i=;i<n;i++) printf("%d%c",kk[i].pay,i==n-?'\n':' ');

     }

 }

1005 Anniversary party

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

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

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int dp[][],t;

 int father[];

 int vis[];

 void solve(int node)

 {

     vis[node]=;

     for(int i=;i<=t;i++)

     {

         if(!vis[i]&&father[i]==node)

         {

             solve(i);

             dp[node][]+=dp[i][];

             dp[node][]+=max(dp[i][],dp[i][]);

         }

     }

 }

 void init()

 {

     memset(dp,,sizeof(dp));

     memset(vis,,sizeof(vis));

     memset(father,,sizeof(father));

 }

 int main()

 {

     while(~scanf("%d",&t))

     {

         init();

         int l,k,root;

         for(int i=;i<=t;i++) scanf("%d",&dp[i][]);

         while(~scanf("%d%d",&l,&k),l||k) father[l]=k;

         for(int i=;i<=t;i++)

             if(!father[i]) root=i;

         solve(root);

         printf("%d\n",max(dp[root][],dp[root][]));

     }

 }

1006 Twin Prime Conjecture

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

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

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #define N 100005

 int ans[N];

 int prime[N];

 int vis[N];

 const int n=;

 int  cnt=,now=;

 void init()

 {

     for(int i=;i<=n;i++)

     {

         ans[i]=now;

         if(vis[i]==)

         {

             prime[cnt]=i;

             if(cnt!=&&prime[cnt]-prime[cnt-]==) now++;

             ans[i]=now;

             cnt++;

         }

         for(int j=;j<cnt&&i*prime[j]<=n;j++)

         {

             vis[i*prime[j]]=true;

             if(i%prime[j]==) break;

         }

     }

 }

 int main()

 {

     init();

     //for(int i=0;i<20;i++) printf("%d\n",ans[i]);

     int n;

     while(~scanf("%d",&n),n>=)

     {

         printf("%d\n",ans[n]);

     }

 }

//1007跑了

1008 Manhattan Sort

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

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

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 struct p{

     int numb,id;

 }a[];

 bool cmp(p x,p y)

 {

     return x.numb<y.numb;

 }

 map<int,int> b;

 int main()

 {

     int t;scanf("%d",&t);

     for(int kk=;kk<=t;kk++)

     {

         int n;scanf("%d",&n);

         for(int i=;i<=n;i++) scanf("%d",&a[i].numb),a[i].id=b[a[i].numb]=i;

         sort(a+,a+n+,cmp);

         int ans=;

         for(int i=;i<=n;i++)

             ans+=abs(i-b[a[i].numb]);

         printf("Case #%d: %d\n",kk,ans/);

     }

 }

1009 SPF

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

割点，困了，再说。

巴特西

2019/11/02 TZOJ

最新文章

热门文章