给二维布局体数组赋值后值自身产生了退换,Day3晚上解题报告

 百家乐-操作     |      2019-12-21 19:40

/*主题材料:错误样例:在i=0,j=2的时候赋值w[i][j].m=2;出了循环w[i][j].m就变成0了;input:424-01-232-031-0output:1-01-2-03*/#includebits/stdc++.husingnamespacestd;structq{intm;doubleq;};structq1{intm;intsex;};intcmp(qx,qy){if(x.q!=y.q){returnx.qy.q;}else{returnabs(x.m)abs(y.m);}}intmain(){ios::sync_with_stdio(false);inta,b;scanf("%d%d",a,b);doublesl[b];q1w[a][b];memset(w,0,sizeof(w));for(inti=0;ib;i++){scanf("%lf",sl[i]);for(intj=0;jsl[i];j++){charr;r=getchar();if(r=='-'){w[i][j].sex=2;intr1=0;r=getchar();while(r='9'r='0'){r1*=10;r1+=r-'0';r=getchar();}w[i][j].m=r1;}else{w[i][j].sex=1;intr2=0;while(r='9'r='0'){r2*=10;r2+=r-'0';r=getchar();}w[i][j].m=r2;}}}q1A;q1B;A.m=0;B.m=0;charA1;charB1;A1=getchar();if(A1=='n'){A1=getchar();}if(A1=='-'){A.sex=2;A1=getchar();while(A1='9'A1='0'){A.m*=10;A.m+=A1-'0';A1=getchar();}}else{A.sex=1;while(A1='9'A1='0'){A.m*=10;A.m+=A1-'0';A1=getchar();}}B1=getchar();if(B1=='-'){B.sex=2;B1=getchar();while(B1='9'B1='0'){B.m*=10;B.m+=B1-'0';B1=getchar();}}else{B.sex=1;while(B1='9'B1='0'){B.m*=10;B.m+=B1-'0';B1=getchar();}}qn[1005];memset(n,0,sizeof(n));qv[1005];memset(v,0,sizeof(v));for(inti=0;i=1000;i++){n[i].m=i;v[i].m=i;}boolflag1=false;boolflag2=false;boolf1=false;boolf2=false;for(inti=0;ib;i++){flag1=false;flag2=false;doubles=1.0;s/=sl[i];for(intj=0;jsl[i];j++){if(flag1flag2){break;}if(w[i][j].m==A.mw[i][j].sex==A.sex){flag1=true;f1=true;}elseif(w[i][j].m==B.mw[i][j].sex==B.sex){flag2=true;f2=true;}}if(flag1){for(intj=0;jsl[i];j++){if(w[i][j].sex==B.sex){n[w[i][j].m].q+=s;}}}if(flag2){for(intj=0;jsl[i];j++){if(w[i][j].sex==A.sex){v[w[i][j].m].q+=s;}}}}doublea1,b1;if(f1){a1=n[B.m].q;sort(n,n+1005,cmp);}if(f2){b1=v[A.m].q;sort(v,v+1005,cmp);}doublenc=n[0].q;doublevc=v[0].q;boolsc=false;if((a1=ncb1=vc)||(!f1!f2)||(nc=n[1].qvc=v[1].q(n[0].m==B.mv[0].m==A.m))){if(A.sex==2){printf("-%d%dn",A.m,B.m);}else{printf("%d-%dn",A.m,B.m);}}else{if(!f1){if(A.sex==2){printf("-%d%dn",A.m,B.m);}else{printf("%d-%dn",A.m,B.m);}}else{for(intj=0;j=1004;j++){if(n[j].qnc){break;}if(n[j].q==nc){if(A.sex==2){printf("-%d%dn",A.m,n[j].m);}else{printf("%d-%dn",A.m,n[j].m);}sc=true;}}}if(!f2){if(A.sex==2){printf("%d-%dn",B.m,A.m);}else{printf("-%d%dn",B.m,A.m);}}else{for(intj=0;j=1004;j++){if(v[j].qvc){break;}if(v[j].q==vc){if(B.sex==2){printf("-%d%dn",B.m,v[j].m);}else{printf("%d-%dn",B.m,v[j].m);}sc=true;}}}}return0;}

猜想分数:100+40+50=190

事实上分数:100+40+50=190

T2

不会做,打40分暴力走人

图片 1 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 #include<ctime> 8 using namespace std; 9 const int MAXN=1e6; 10 const int INF=0x7ffff; 11 inline int read() 12 { 13 char c=getchar();int flag=1,x=0; 14 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();} 15 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag; 16 } 17 const int mod=1e9+7; 18 int a[MAXN]; 19 int ans[MAXN]; 20 int anstot=0; 21 int comp(const int &a,const int &b) 22 { 23 return a>b; 24 } 25 int main() 26 { 27 //freopen("war.in","r",stdin); 28 //freopen("war.out","w",stdout); 29 int n=read(),k=read(); 30 if(n<=3000) 31 { 32 for(int i=1;i<=n;i++) a[i]=read(); 33 for(int i=1;i<=n;i++) 34 for(int j=i+1;j<=n;j++) 35 if(i!=j) 36 ans[++anstot]=a[i]^a[j]; 37 sort(ans+1,ans+anstot+1,comp); 38 int out=0; 39 for(int i=1;i<=k;i++) 40 out=(out+ans[i])%mod; 41 printf("%d",out); 42 } 43 else if(k==1) 44 { 45 for(int i=1;i<=n;i++) a[i]=read(); 46 int t=clock(); 47 sort(a+1,a+n+1,comp); 48 int ans=0; 49 for(int i=1;i<=n;i++) 50 { 51 for(int j=i+1;j<=n;j++) 52 { 53 ans=max(ans,(a[i]^a[j])%mod)%mod; 54 if(clock()-t>=900) 55 { 56 printf("%d",ans); 57 exit(0); 58 } 59 } 60 } 61 printf("%d",ans); 62 } 63 else 64 { 65 int t=clock(); 66 for(int i=1;i<=n;i++) a[i]=read(); 67 for(int i=1;i<=n;i++) 68 for(int j=i+1;j<=n;j++) 69 if(i!=j) 70 { 71 ans[++anstot]=a[i]^a[j]; 72 if(clock()-t>=800) 73 { 74 sort(ans+1,ans+anstot+1,comp); 75 int out=0; 76 for(int i=1;i<=k;i++) 77 out=(out+ans[i])%mod; 78 printf("%d",out); 79 } 80 } 81 sort(ans+1,ans+anstot+1,comp); 82 int out=0; 83 for(int i=1;i<=k;i++) 84 out=(out+ans[i])%mod; 85 printf("%d",out); 86 } 87 return 0; 88 } 40暴力

正解:

20分k==1

参天位异或==1

若果最大的数独有4位

把全体数遍历生龙活虎边,看一下第三个人是0如故1

考虑分治,对于曾经规定的要职,在能选取的间隔中观看低一个人的可以还是不可以改为1

最长区间为n

复杂度$O(31*n)$

20分不当先1023

记录0-1023的各个数有多少个

历次暴力枚举

$cnt[a^b]+=cnt[a]*cnt[b]$

正解:

01 trie树

先算第k大是甚,再把比他大的加起来

思谋怎么求k->二分

哪些求比k大的数:

枚举一个i,那么难题就转会为求某个许个j使得a[i]^a[j]>v(二分的值卡塔尔国

用trie树,从高高的位起先枚举

看tire树的右孙子(1卡塔尔有稍许个节点

 

 

图片 2 1 #define PROC "shana" 2 #include <cstdio> 3 #include <cctype> 4 #include <memory.h> 5 #include <algorithm> 6 #include<cctype> 7 8 using namespace std; 9 10 typedef long long qw; 11 12 #define _l (qw) 13 const int BUF_SIZE = 30; 14 char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1; 15 16 #define PTR_NEXT() 17 { 18 buf_s ++; 19 if (buf_s == buf_t) 20 { 21 buf_s = buf; 22 buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); 23 } 24 } 25 26 #define readInt(_n_) 27 { 28 while (*buf_s != '-' && !isdigit(*buf_s)) 29 PTR_NEXT(); 30 bool register _nega_ = false; 31 if (*buf_s == '-') 32 { 33 _nega_ = true; 34 PTR_NEXT(); 35 } 36 int register _x_ = 0; 37 while (isdigit(*buf_s)) 38 { 39 _x_ = _x_ * 10 + *buf_s - '0'; 40 PTR_NEXT(); 41 } 42 if (_nega_) 43 _x_ = -_x_; 44 (_n_) = (_x_); 45 } 46 47 const int maxn = 50010; 48 const int maxl = 31; 49 const int maxnd = maxn * maxl; 50 const int mod = 1e9 + 7; 51 const int inv = 500000004; 52 53 int v0, n, rt, tn, a[maxn]; 54 int tr[maxnd][2], rb[maxnd][maxl], c[maxnd]; 55 qw k; 56 57 void trieIns(int v) { 58 int p = rt; 59 for (int i = maxl - 1; i >= 0; -- i) { 60 int v0 = (v >> i) & 1; 61 if (!tr[p][v0]) 62 tr[p][v0] = ++ tn; 63 p = tr[p][v0]; 64 ++ c[p]; 65 for (int j = maxl - 1; j >= 0; -- j) 66 if ((v >> j) & 1) 67 ++ rb[p][j]; 68 } 69 } 70 71 int cntUpper(int v, int vu) { 72 int p = rt, s = 0; 73 for (int i = maxl - 1; i >= 0; -- i) { 74 int v0 = (v >> i) & 1; 75 if ((vu >> i) & 1) { 76 p = tr[p][v0 ^ 1]; 77 } 78 else { 79 s += c[tr[p][v0 ^ 1]]; 80 p = tr[p][v0]; 81 } 82 } 83 return s; 84 } 85 86 qw check(int v) { 87 qw s = 0; 88 for (int i = 0; i < n; ++ i) 89 s += cntUpper(a[i], v); 90 return s >> 1; 91 } 92 93 int sumUpper(int v, int vu) { 94 int s = 0, p = rt; 95 for (int i = maxl - 1; i >= 0; -- i) { 96 int v0 = (v >> i) & 1; 97 if ((vu >> i) & 1) 98 p = tr[p][v0 ^ 1]; 99 else { 100 for (int j = 0; j < maxl; ++ j) 101 if ((v >> j) & 1) 102 s = (_l s + (1LL << j) * (_l c[tr[p][v0 ^ 1]] - _l rb[tr[p][v0 ^ 1]][j])) % mod; 103 else 104 s = (_l s + (1LL << j) * _l rb[tr[p][v0 ^ 1]][j]) % mod; 105 p = tr[p][v0]; 106 } 107 } 108 return s; 109 } 110 111 int main() { 112 freopen("war.in", "r", stdin); 113 freopen("war.out", "w", stdout); 114 115 readInt(n); 116 readInt(k); 117 rt = 1; 118 tn = 1; 119 for (int i = 0; i < n; ++ i) { 120 readInt(a[i]); 121 trieIns(a[i]); 122 } 123 { 124 int l = 0, r = 2147483647; 125 while (l < r) { 126 int mid = (_l l + r + 1) >> 1; 127 if (check(mid - 1) < k) 128 r = mid - 1; 129 else 130 l = mid; 131 } 132 v0 = l; 133 } 134 if (v0) { 135 //printf("%d %lldn", v0, check(v0)); 136 int ans = 0; 137 for (int i = 0; i < n; ++ i) 138 ans = (_l ans + sumUpper(a[i], v0 - 1)) % mod; 139 ans = (_l ans * inv % mod + ((k - check(v0 - 1)) % mod + mod) * _l v0) % mod; 140 printf("%dn", ans); 141 } 142 else { 143 int ans = 0; 144 for (int i = 0; i < n; ++ i) 145 ans = (_l ans + sumUpper(a[i], 0)) % mod; 146 ans = _l ans * inv % mod; 147 printf("%dn", ans); 148 } 149 } View Code

 

Day3早上解题报告,day3早上解题

 

T1

意味着一直没做过博艺论的题,

唯独在推了40多分钟今后开掘存几个结论是任其自然没错。。。。

n,m都是奇数,后手胜

再不先手胜

图片 3 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=1e6; 7 const int INF=0x7ffff; 8 inline int read() 9 { 10 char c=getchar();int flag=1,x=0; 11 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();} 12 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag; 13 } 14 int main() 15 { 16 // freopen("star.in","r",stdin); 17 // freopen("star.out","w",stdout); 18 int n,m; 19 while(scanf("%d%d",&n,&m)) 20 { 21 if(n==0&&m==0) break; 22 int nowx=n,nowy=1; 23 if(n%2==0)//A不利 24 { 25 printf("Yurin"); 26 } 27 else 28 { 29 if(m%2==0) printf("Yurin"); 30 else printf("Chiton"); 31 } 32 } 33 return 0; 34 } View Code

上一篇:没有了 下一篇:没有了