[关闭]
@baobaobear 2020-02-11T03:46:45.000000Z 字数 8573 阅读 176

Contest14

contest

A puluo

  1. #include<stdio.h>
  2. int main()
  3. {
  4.     int a,b,t; 
  5.     scanf("%d%d%d",&a,&b,&t);
  6.     printf("%d\n",(t/a)*b);
  7. }

B puluo

  1. #include<stdio.h>
  2. int main()
  3. {
  4.     int n,a,sum=0;
  5.     scanf("%d",&n);
  6.     for(int i=0;i<n;i++)
  7.     {
  8.         scanf("%d",&a);
  9.         sum+=a;
  10.     }
  11.     sum-=n;
  12.     printf("%d\n",sum);
  13. }

C puluo

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. int a[100005];
  4. int inc(const void *a, const void *b)
  5. {
  6.     return *(int *)a-*(int *)b;
  7. }
  8. int main()
  9. {
  10.     int n,m,min=-1;
  11.     scanf("%d%d",&n,&m);
  12.     for(int i=0;i<n;i++)scanf("%d",&a[i]);
  13.     qsort(a,n,sizeof(int),inc);
  14.     for(int i=0;i<=(n-m);i++)
  15.     {
  16.         if(min==-1)min=a[i+m-1]-a[i];
  17.         if(min>a[i+m-1]-a[i])min=a[i+m-1]-a[i];
  18.     }
  19.     printf("%d\n",min);
  20. }

D lnkkerst

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <algorithm>
  4. #define int long long
  6. struct Monster {
  7.     int x, h, dam;
  8. } a[200010];
  10. int n, d, s, ans = 0;
  12. int read() {
  13.     int ret, f = 1;
  14.     char ch;
  15.     while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
  16.     for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
  17.     return ret * f;
  18. }
  20. void print(int x) {
  21.     if(x < 0) putchar('-'), x = -x;
  22.     if(x > 9) print(x / 10);
  23.     putchar(x % 10 + '0');
  24. }
  26. bool cmp(Monster a, Monster b) {
  27.     return a.x < b.x;
  28. }
  30. signed main() {
  31.     n = read(), d = read(), s = read();
  32.     for(int i = 1; i <= n; ++i) a[i].x = read(), a[i].h = read();
  33.     std::sort(a + 1, a + n + 1, cmp);
  34.     for(int i = 1; i <= n; ++i) {
  35.         a[i].dam += a[i - 1].dam;
  36.         int l = i, r = i + (d << 1);
  37.         if(r > n) r = n;
  38.         while(l < r) {
  39.             int mid = (l + r + 1) >> 1;
  40.             if(a[mid].x <= a[i].x + (d << 1)) l = mid;
  41.             else r = mid - 1;
  42.         }
  43.         int tmp = (a[i].h - a[i].dam * s + s - 1) / s;
  44.         if(tmp < 0) continue;
  45.         ans += tmp, a[i].dam += tmp, a[l + 1].dam -= tmp;
  46.     }
  47.     print(ans);
  48.     return 0;
  49. }

E lnkkerst

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <cstring>
  4. #define int long long
  6. struct Trie {
  7.     int cnt, root, go[8000000][10], val[8000000];
  8.     Trie() {
  9.         memset(go, 0, sizeof(go));
  10.         memset(val, 0, sizeof(val));
  11.         root = cnt = 0;
  12.     }
  13.     void add(int num, int v) {
  14.         int now = root;
  15.         while(num) {
  16.             int k = num % 10;
  17.             if(!go[now][k]) go[now][k] = ++cnt;
  18.             now = go[now][k], num /= 10;
  19.         }
  20.         val[now] += v;
  21.     }
  22.     int query(int num) {
  23.         int now = root;
  24.         while(num) {
  25.             int k = num % 10;
  26.             if(!go[now][k]) return 0;
  27.             now = go[now][k], num /= 10;
  28.         }
  29.         return val[now];
  30.     }
  31. } b;
  33. int n, k, ans = 0;
  34. int fs[200010];
  36. int read() {
  37.     int ret, f = 1;
  38.     char ch;
  39.     while(!isdigit(ch = getchar())) (ch == '-') && (f = -1);
  40.     for(ret = ch - '0'; isdigit(ch = getchar()); ret *= 10, ret += ch - '0');
  41.     return ret * f;
  42. }
  44. void print(int x) {
  45.     if(x < 0) putchar('-'), x = -x;
  46.     if(x > 9) print(x / 10);
  47.     putchar(x % 10 + '0');
  48. }
  50. signed main() {
  51.     n = read(), k = read();
  52.     for(int i = 1; i <= n; ++i) fs[i] = fs[i - 1] + read();
  53.     b.add(0, 1);
  54.     int j = 0;
  55.     for(int i = 1; i <= n; ++i) {
  56.         if(i >= k) b.add((fs[j] - j + k) % k, -1), ++j;
  57.         ans += b.query((fs[i] - i + k) % k);
  58.         b.add((fs[i] - i + k) % k, 1);
  59.     }
  60.     print(ans);
  61.     return 0;
  62. }

F 1292224662

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int a,b;
  4. char mp[105][105];
  5. int main(){
  6.     cin>>a>>b;
  7.     for(int i=1;i<=50;i++){
  8.         for(int j=1;j<=100;j++){
  9.             mp[i][j]='.';
  10.         }
  11.     }
  12.     for(int i=51;i<=100;i++){
  13.         for(int j=1;j<=100;j++){
  14.             mp[i][j]='#';
  15.         }
  16.     }
  17.     a--;b--;
  18.     for(int i=1;i<=49&&b;i+=2){
  19.         for(int j=1;j<=100&&b;j++){
  20.             if(mp[i-1][j]!='#'&&mp[i][j-1]!='#'){
  21.                 mp[i][j]='#';b--;
  22.             }
  23.         }
  24.     }
  25.     for(int i=52;i<=100&&a;i+=2){
  26.         for(int j=1;j<=100&&a;j++){
  27.             if(mp[i-1][j]!='.'&&mp[i][j-1]!='.'){
  28.                 mp[i][j]='.';a--;
  29.             }
  30.         }
  31.     }
  32.     puts("100 100");
  33.     for(int i=1;i<=100;i++){
  34.         puts(mp[i]+1);
  35.     }
  36.     return 0;
  37. }

G 541907010220

  1. #include<iostream>
  2. using namespace std;
  3. int a[500001];
  4. #define inf 0x3f3f3f3f
  5. int main()
  6. {
  7.     int n,s,i,j,ans=inf;
  8.     cin>>s>>n;
  9.     for(i=1;i<=n;i++)
  10.     {
  11.         scanf("%d",&a[i]);
  12.     }
  13.     int qq=ans;
  14.     int sum=0;
  15.     int l=1;
  16.     for(i=1;i<=n;i++)
  17.     {
  18.         if(sum<s)
  19.         sum+=a[i];
  20.         while(sum>=s)
  21.         {
  22.             ans=min(ans,i-l+1);
  23.             sum-=a[l];
  24.             l++;
  26.         }
  27.         if(i<l)
  28.         i++;
  29.      }
  30.      if(ans==qq)cout<<0;
  31.      else cout<<ans;
  32.      return 0;
  33.  }

H hesorchen

  1. #include <iostream>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <queue>
  5. #include <string>
  6. #include <algorithm>
  7. using namespace std;
  8. #define ll long long
  9. char mp[2005][2005];
  10. int mp_zong[2005][2005];
  11. int mp_heng[2005][2005];
  12. int n, m;
  13. int maxx = 0;
  14. int main()
  15. {
  16.     ll maxx_ans = 0;
  17.     cin >> n >> m;
  18.     for (int i = 1; i <= n; i++)
  19.         cin >> mp[i] + 1;
  20.     for (int i = 1; i <= n; i++)
  21.         for (int j = 1; j <= m; j++)
  22.             if (mp[i][j] == '.')
  23.             {
  24.                 if (mp_zong[i][j] == 0)
  25.                 {
  26.                     int num = 0;
  27.                     int minn = 1, maxx = n;
  28.                     for (int k = i; k <= n; k++)
  29.                         if (mp[k][j] == '#')
  30.                         {
  31.                             maxx = k - 1;
  32.                             break;
  33.                         }
  34.                         else
  35.                             num++;
  36.                     for (int k = i - 1; k >= 1; k--)
  37.                         if (mp[k][j] == '#')
  38.                         {
  39.                             minn = k + 1;
  40.                             break;
  41.                         }
  42.                         else
  43.                             num++;
  44.                     for (int l = minn; l <= maxx; l++)
  45.                         mp_zong[l][j] = num;
  46.                 }
  47.                 if (mp_heng[i][j] == 0)
  48.                 {
  49.                     int num = 0;
  50.                     int minn = 1, maxx = m;
  51.                     for (int k = j; k <= m; k++)
  52.                         if (mp[i][k] == '#')
  53.                         {
  54.                             maxx = k - 1;
  55.                             break;
  56.                         }
  57.                         else
  58.                             num++;
  59.                     for (int k = j - 1; k >= 1; k--)
  60.                         if (mp[i][k] == '#')
  61.                         {
  62.                             minn = k + 1;
  63.                             break;
  64.                         }
  65.                         else
  66.                             num++;
  67.                     for (int l = minn; l <= maxx; l++)
  68.                         mp_heng[i][l] = num;
  69.                 }
  70.                 // printf("%d %d %d %d   %d\n", i, j, mp_heng[i][j], mp_zong[i][j], mp_heng[i][j] + mp_zong[i][j] - 1);
  71.                 if (mp_heng[i][j] + mp_zong[i][j] - 1 > maxx_ans)
  72.                     maxx_ans = mp_heng[i][j] + mp_zong[i][j] - 1;
  73.             }
  74.     cout << maxx_ans << endl;
  76.     return 0;
  77. }

I 1292224662

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int m,k; 
  4. int main(){
  5.     cin>>m>>k;
  6.     int tmp=(1<<m)-1;
  7.     if(m==0&&k==0){
  8.         puts("0 0");
  9.         return 0;
  10.     }
  11.     if(k<=tmp){
  12.         if(m==1&&k==1){
  13.             puts("-1");
  14.             return 0;
  15.         }
  16.         if(!k){
  17.             for(int i=0;i<=tmp;i++){
  18.                 printf("%d %d%c",i,i,(i==tmp)?'\n':' ');
  19.             }
  20.         }
  21.         else{
  22.             printf("0 %d 0 ",k);
  23.             for(int i=1;i<=tmp;i++){
  24.                 if(i==k) continue;
  25.                 printf("%d ",i);
  26.             }
  27.             printf("%d ",k);
  28.             for(int i=tmp;i>=1;i--){
  29.                 if(i==k) continue;
  30.                 printf("%d ",i);
  31.             }putchar('\n');
  32.         }
  33.     }
  34.     else{
  35.         puts("-1");
  36.     }
  37.     return 0;
  38. }

J 1292224662

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef double db;
  4. typedef long long ll;
  5. ll n,xx[10],yy[10];
  6. db ans;
  7. ll dis(int i,int j){
  8.     return (xx[i]-xx[j])*(xx[i]-xx[j])+(yy[i]-yy[j])*(yy[i]-yy[j]); 
  9. }
  10. int main(){
  11.     cin>>n;
  12.     for(int i=1;i<=n;i++){
  13.         cin>>xx[i]>>yy[i];
  14.     }
  15.     for(int i=1;i<=n;i++){
  16.         for(int j=i+1;j<=n;j++){
  17.             ans+=sqrt(dis(i,j));
  18.         }
  19.     }
  20.     printf("%.10f\n",(db)2/n*ans);
  21.     return 0;
  22. }

K 1292224662

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int h,w,n;
  4. char mp[30][30];
  5. int vis[30][30],dis[30][30];
  6. int f(int x,int y){
  7.     return (x-1)*w+y;
  8. }
  9. bool ok(int x,int y){
  10.     if(x==0||x>h||y==0||y>w||vis[x][y]||mp[x][y]=='#')
  11.         return false;
  12.     return true;
  13. }
  14. int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
  15. queue<int> qx,qy;
  16. void bfs(){
  17.     while(!qx.empty()){
  18.         int xx=qx.front(),yy=qy.front();
  19.         qx.pop();qy.pop();
  20.         for(int o=0;o<4;o++){
  21.             int xto=xx+dx[o],yto=yy+dy[o];
  22.             if(ok(xto,yto)){
  23.                 dis[xto][yto]=min(dis[xto][yto],dis[xx][yy]+1);
  24.                 vis[xto][yto]=1;
  25.                 qx.push(xto);qy.push(yto);
  26.             }
  27.         }
  28.     }
  29. } 
  30. int main(){
  31.     cin>>h>>w;
  32.     for(int i=1;i<=h;i++){
  33.         scanf("%s",mp[i]+1);
  34.     }
  35.     int mx=0;
  36.     for(int i=1;i<=h;i++){
  37.         for(int j=1;j<=w;j++){
  38.             if(mp[i][j]=='#'){
  39.                 continue;
  40.             }
  41.             memset(vis,0,sizeof(vis));
  42.             memset(dis,0x3f3f3f3f,sizeof(dis));
  43.             qx.push(i);qy.push(j);
  44.             dis[i][j]=0;vis[i][j]=1;
  45.             bfs();
  46.             int mmx=-1;
  47.             for(int p=1;p<=h;p++){
  48.                 for(int q=1;q<=w;q++){
  49.                     if(mp[p][q]=='#')continue;
  50.                     mmx=max(mmx,dis[p][q]);
  51.                 }
  52.             }
  53.             mx=max(mx,mmx);
  54.         }
  55.     }
  56.     cout<<mx<<endl;
  57.     return 0;
  58. }

L xiaofan7

  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <map>
  6. #include <set>
  7. #include <queue>
  8. #include <stack>
  9. #include <algorithm>
  10. #include <cstdlib>
  11. #include <cmath>
  12. #include <vector>
  13. #include <iomanip>
  14. #if __cplusplus >= 201103L
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #endif
  18. #define ls x*2
  19. #define rs x*2+1
  20. #define fi first
  21. #define se second
  22. #define ll long long
  23. #define pb push_back
  24. #define vi vector<int>
  25. #define lowbit(x) x&(-x)
  26. #define pii pair<int,int>
  27. #define umap unordered_map
  28. #define uset unordered_set
  29. #define all(x) x.begin(),x.end()
  30. #define mem(a,b) memset(a,b,sizeof(a))
  31. #define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
  33. using namespace std;
  35. const int INF = 0x3f3f3f3f;
  37. ll get(ll a) {
  38.     if(a%4==1)
  39.         return 1;
  40.     else if(a%4==2)
  41.         return a+1;
  42.     else if(a%4==3||a==0)
  43.         return 0;
  44.     else
  45.         return a;
  46. }
  48. int main() {
  49.     IOS;
  50. #ifdef xiaofan
  51.     freopen("in.txt","r",stdin);
  52. #endif
  54.     ll a,b;
  55.     cin>>a>>b;
  56.     ll ans=get(b)^get(a-1);
  57.     if(a==0){
  58.         if(b==0)ans=0;
  59.         else ans=get(b);
  60.     }
  61.     cout<<ans<<endl;
  65. #ifdef xiaofan
  66.     cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  67. #endif
  68.     return 0;
  69. }

M puluo

  1. #include<stdio.h>
  2. #include<math.h>
  3. #define N 100000000
  4. #define M 100005
  5. int main()
  6. {
  7.     int n;
  8.     double x[M],y[M];
  9.     char c[M];
  10.     double minS=-1,S1,S2,l=0,r=N;
  11.     double minl1=N,maxr1=-N,maxu1=-N,mind1=N,xx1,yy1,move1=0;
  12.     double minl2=N,maxr2=-N,maxu2=-N,mind2=N,xx2,yy2,move2=N;
  13.     scanf("%d",&n);
  14.     for(int i=0;i<n;i++)scanf("%lf%lf %c",&x[i],&y[i],&c[i]);
  15.     for(int k=0;k<=10000&&(move2-move1>0.00000000001);k++)
  16.     {
  17.         minl1=N,maxr1=-N,maxu1=-N,mind1=N;
  18.         minl2=N,maxr2=-N,maxu2=-N,mind2=N;
  19.         move1=(r/3+2*l/3),move2=(2*r/3+l/3);
  20.         for(int i=0;i<n;i++)
  21.         {
  22.             xx1=xx2=x[i];
  23.             yy1=yy2=y[i];
  24.             if(c[i]=='U')
  25.             {
  26.                 yy1+=move1;
  27.                 yy2+=move2;
  28.             }
  29.             if(c[i]=='D')
  30.             {
  31.                 yy1-=move1;
  32.                 yy2-=move2;
  33.             }
  34.             if(c[i]=='L')
  35.             {
  36.                 xx1-=move1;
  37.                 xx2-=move2;
  38.             }
  39.             if(c[i]=='R')
  40.             {
  41.                 xx1+=move1;
  42.                 xx2+=move2;
  43.             }
  44.             if(xx1<minl1)minl1=xx1;
  45.             if(xx1>maxr1)maxr1=xx1;
  46.             if(yy1<mind1)mind1=yy1;
  47.             if(yy1>maxu1)maxu1=yy1;
  48.             if(xx2<minl2)minl2=xx2;
  49.             if(xx2>maxr2)maxr2=xx2;
  50.             if(yy2<mind2)mind2=yy2;
  51.             if(yy2>maxu2)maxu2=yy2;
  52.         }
  53.         S1=(maxr1-minl1)*(maxu1-mind1);
  54.         S2=(maxr2-minl2)*(maxu2-mind2);
  55.         if(S1<minS||minS==-1)minS=S1;
  56.         if(S2<minS||minS==-1)minS=S2;
  57.         if(S1>S2)l=move1;
  58.         else r=move2;
  59.     }
  60.     printf("%.10f\n",minS);
  61. }

N 1292224662

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll n,a[10010];
  5. ll fac[1000010];
  6. const ll mod=1e9+7;
  7. ll sqr(ll x){   //sqr(5)=2,sqr(10)=3
  8.     ll lft=0,rht=1e5;
  9.     while(rht-lft>1){
  10.         ll mid=(rht+lft)>>1;
  11.         if(mid*mid<=x){
  12.             lft=mid;
  13.         }
  14.         else{
  15.             rht=mid;
  16.         }
  17.     }
  18.     return lft;
  19. }
  20. ll qp(ll a,ll b,ll mod){
  21.     ll ans=1;
  22.     while(b){
  23.         if(b&1)
  24.             ans=ans*a%mod;
  25.         a=a*a%mod;
  26.         b>>=1;
  27.     }
  28.     return ans;
  29. }
  30. ll getInv(ll x,ll p){
  31.     return qp(x,p-2,p);
  32. }
  33. int main(){
  34.     cin>>n;
  35.     for(int i=1;i<=n;i++){
  36.         cin>>a[i];
  37.         int tmp=a[i],bound=sqr(a[i]);
  38.         for(int j=2;j<=bound;j++){
  39.             if(tmp%j==0){
  40.                 ll save=0;
  41.                 while(tmp%j==0){
  42.                     tmp/=j;
  43.                     save++;
  44.                 }
  45.                 fac[j]=max(fac[j],save);
  46.                 j=1;bound=sqr(tmp);
  47.             }
  48.         }
  49.         if(tmp!=1){
  50.             fac[tmp]=max(fac[tmp],1ll);
  51.         }
  52.     }
  53.     ll sum=1;
  54.     for(int i=2;i<=1000005;i++){
  55.         sum=sum*qp(i,fac[i],mod)%mod;
  56.     }
  57.     ll ans=0;
  58.     for(int i=1;i<=n;i++){
  59.         ans=ans+getInv(a[i],mod)*sum%mod;
  60.         ans%=mod; 
  61.     }
  62.     cout<<ans<<endl;
  63.     return 0;
  64. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注