title: ACM-NEFU15届校赛-大二组
tags:

  • ACM
    abbrlink: 8a3e9951
    date: 2020-12-09 17:46:31

A.小林找工作

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. const int MAXN=1e5+10;
  6. int p[MAXN];
  8. int main()
  9. {
  10.     int n,m;
  11.     cin>>n>>m;
  12.     for(int i=1;i<=n;i++)
  13.     {
  14.         scanf("%d", &p[i]);
  15.     }
  16.     sort(p+1,p+n+1);
  17.     for(int i=0;i<m;i++)
  18.     {
  19.         int temp;
  20.         scanf("%d", &temp);
  21.         int pos=lower_bound(p+1,p+n+1,temp)-p;
  22.         if(pos>n)    pos=n;
  23.         int ans=abs(temp-p[pos]);
  24.         if(pos!=1)    ans=min(ans, abs(temp-p[pos-1]));
  25.         printf("%d\n", ans);
  26.     }
  27.     return 0;
  28. }

B.xx的树

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. const int MAXN=2e5+10;
  6. typedef long long ll;
  8. typedef struct{
  9.     int to;
  10.     int next;
  11. }edge;
  13. edge e[MAXN];
  14. int cur=1,head[MAXN],vis[MAXN];
  15. ll value[MAXN];
  17. void add(int u,int v)
  18. {
  19.     e[cur].to=v;
  20.     e[cur].next=head[u];
  21.     head[u]=cur++;
  22. }
  24. void dfs(int u)
  25. {
  26.     vis[u]=1;
  27.     for(int i=head[u];i!=0;i=e[i].next)
  28.     {
  29.         int v=e[i].to;
  30.         if(vis[v])    continue;
  31.         value[v]+=value[u];
  32.         dfs(v);
  33.     }
  34. }
  36. int main()
  37. {
  38.     int n,m;
  39.     cin>>n>>m;
  40.     for(int i=1;i<n;i++)
  41.     {
  42.         int u,v;
  43.         cin>>u>>v;
  44.         add(u,v);
  45.         add(v,u);
  46.     }
  47.     for(int i=1;i<=m;i++)
  48.     {
  49.         ll u,d;
  50.         cin>>u>>d;
  51.         value[u]+=d;
  52.     }
  53.     dfs(1);
  54.     for(int i=1;i<=n;i++)
  55.         i==1?cout<<value[i]:cout<<" "<<value[i];
  56.     return 0;
  57. }

C.xx玩游戏

找到规律，偶数列没有必败态，奇数列有（n+1）/2个必败态

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. typedef long long ll;
  7. int main()
  8. {
  9.     int t;
  10.     cin>>t;
  11.     while(t--)
  12.     {
  13.         ll n;
  14.         scanf("%lld", &n);
  15.         ll t=(n+1)/2;
  16.         ll lose=(1+t)*t/2;
  17.         ll sum=(1+n)*n/2;
  18.         printf("%lld\n", sum-lose);
  19.     }
  20.     return 0;
  21. }

D. xx的零食店(待补)

E.qyh的签到题

跟去年校赛大一的一道题神似…

  1. #include<bits/stdc++.h>
  3. using namespace std;
  5. int n,q;
  6. typedef long long ll;
  7. const long long mod=1e9+7;
  8. const int MAXN=1e5+5;
  9. ll d1[MAXN],d2[MAXN],d3[MAXN];
  11. void pre_sum(ll d[])
  12. {
  13.     for(int i=1;i<=n;i++)
  14.     {
  15.         d[i]+=d[i-1];
  16.         d[i]%=mod;
  17.     }
  18. }
  20. int main()
  21. {
  22.     scanf("%d%d",&n, &q);
  23.     for(int i=0;i<q;i++)
  24.     {
  25.         int type,pos;
  26.         scanf("%d%d", &type, &pos);
  27.         if(type==1)    d1[pos]++;
  28.         if(type==2)    d2[pos]++;
  29.         if(type==3)
  30.         {
  31.             d3[pos]++;
  32.             d3[pos+1]++;
  33.         }
  34.     }
  35.     pre_sum(d3);    pre_sum(d3);    pre_sum(d3);
  36.     pre_sum(d2);    pre_sum(d2);
  37.     pre_sum(d1);
  38.     for(int i=1;i<=n;i++)
  39.     {
  40.         i==1?printf("%lld", (d1[i]+d2[i]+d3[i])%mod):printf(" %lld", (d1[i]+d2[i]+d3[i])%mod);
  41.     }
  42.     return 0;
  43. }

G.天哥的序列