一，分数报告
| T1 | 100分 |
| T2 | 100分 |
| T3 | 0分 |
| T4 | 20分 |
| 总分 | 220分 |
二，赛中概括
前两题1小时做完。后两题骗了20分。
三，题目解析
三个（three）
1.1 问题描述
现在科学家在培养 A,B,C三种微生物，这三种微生物每一秒都会繁殖出新的微生物，具体规则为：
A类微生物每一秒会繁殖出 1个 A 类微生物，1 个 B 类微生物，1 个 C 类微生物。
B 类微生物每一秒会繁殖出 2 个 A 类微生物，2 个 C 类微生物。
C 类微生物每一秒会繁殖出 1 个 A 类微生物，1 个 B 类微生物。假设所有的微生物都不会死亡，一开始培养皿中有 A,B,C 三种微生物各 1 个，现在问你 n 秒后 A,B,C 三种微生物分别有奇数个还是偶数个。
1.2 输入格式
从文件
three.in中读取数据。一行一个整数 nn。
1.3 输出格式
输出到文件
three.out中。输出总共三行：
第一行：若 n 秒后 A 类微生物有奇数个，输出
odd，否则输出even。
第二行：若 n 秒后 B 类微生物有奇数个，输出odd，否则输出even。
第三行：若 n 秒后 C 类微生物有奇数个，输出odd，否则输出even。1.4 输入样例1
5 1.5 输出样例1
odd odd odd 1.6 输入样例2
4 1.7 输出样例2
odd odd even 1.8 输入样例3
233 1.9 输出样例3
even even odd 1.10 数据描述
总共 20 个测试点：
对于测试点 1∼4： 1≤n≤3。 对于测试点 5∼8： 1≤n≤100。 对于测试点 9∼20： 1≤n≤10^6。 一道暴力水题，注意开long long，否则大数据爆掉。
AC代码
#include<bits/stdc++.h>
using namespace std;
long long n,a[1000006],b[1000006],c[1000006];
int main(){//freopen("three.in","r",stdin);别写错！！！！！！//freopen("three.out","w",stdout);cin>>n;a[0]=b[0]=c[0]=1;for(int i=1;i<=n;i++){a[i]=a[i-1]*2+b[i-1]*2+c[i-1];//累加微生物a,b,c的数量。b[i]=a[i-1]+c[i-1]+b[i-1];c[i]=a[i-1]+b[i-1]*2+c[i-1];}if(a[n]%2==0){//判断奇偶cout<<"even";}else{cout<<"odd";}cout<<'\n';if(b[n]%2==0){cout<<"even";}else{cout<<"odd";}cout<<'\n';if(c[n]%2==0){cout<<"even";}else{cout<<"odd";}fclose(stdin);fclose(stdout);return 0;
} 合体（fit）
2.1 问题描述
现在有 n 个大小范围在 1∼m 中的整数 a1∼an，并且你获得了一项魔法能力。
施加一次魔法能力后，可以将两个相同的数字合并成一个数字，并且这个数字为原来的数字 +1，例如：有 2,2 这两个数字，施加一次魔法能力后可以将这两个数字合并成一个数字 3。
现在有 q 次询问，每次询问给你一个整数 x，你可以施加任意次数魔法能力，问你这 n 个整数最多能得到多少个整数 x？
2.2 输入格式
从文件
fit.in中读取数据。第一行两个整数 n,m。
第二行 nn 个整数 a1,a2,a3∼an。
第三行一个整数 q。
接下来 q 行，每行一个整数 x。2.3 输出格式
输出到文件
fit.out中。输出 q 行，对于每个询问，输出对应的答案。
2.4 输入样例
10 4 // // // // // // // // 1 1 1 2 1 3 4 1 2 3 5 // // // // // // // // // 1 // // // // // // // // // 2 // // // // // // // // // 3 // // // // // // // // // 4 // // // // // // // // // 4 // // // // // // // // // 2.5 输出样例
5 4 4 3 3 2.6 数据描述
总共 20 个测试点：
对于测试点 1∼4: 1≤n≤10,1≤m≤10,1≤ai≤m,1≤q≤10,1≤x≤m 对于测试点 5∼6: 1≤n≤10^6,m=1,ai=1,q=1,x=1 对于测试点 7∼8: 1≤n≤10^6,m=5,1≤ai≤m,1≤x≤m,1≤q≤m 对于测试点 9∼20: 1≤n≤10^6,1≤m≤10^6,1≤ai≤m,1≤x≤m,1≤q≤m 桶排序求合并后，打表求结果。差不多是
你会AK-IOI吗？
死铁
原版2048
70分代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1000006],b[1000006],c[1000006],d[1000006],q,e[1000006];
int main(){freopen("fit.in","r",stdin);freopen("fit.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);b[a[i]]++;c[a[i]]++;}for(int i=1;i<m;i++){c[i+1]+=c[i]/2;c[i]%=2;}for(int i=1;i<=m;i++){d[i]=c[i]-b[i];}long long cnt=0;cin>>q;while(q--){int x;scanf("%d",&x);for(int i=m;i>=x;i--){e[i]=c[i]+cnt;cnt=cnt*2;cnt+=2*d[i];}printf("%lld\n",e[x]);}fclose(stdin);fclose(stdout);return 0;
}
AC代码AK-IOI
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1000006],b[1000006],c[1000006],d[1000006],q,e[1000006];
int main(){freopen("fit.in","r",stdin);freopen("fit.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);b[a[i]]++;//合并前c[a[i]]++;}for(int i=1;i<m;i++){//合并后c[i+1]+=c[i]/2;c[i]%=2;}for(int i=1;i<=m;i++){d[i]=c[i]-b[i];}long long cnt=0;for(int i=m;i>=1;i--){//打表过样例e[i]=c[i]+cnt;cnt=cnt*2;cnt+=2*d[i];}cin>>q;while(q--){int x;scanf("%d",&x);printf("%lld\n",e[x]);}fclose(stdin);fclose(stdout);return 0;
} 矩阵（matrix）
3.1 问题描述
现在给你一个 n 行 m 列的矩阵，矩阵上每个格子有一个整数，其中第 i 行第 j 列对应的格子上的整数为 gi,j。
现在定义该矩阵的一个子矩阵的快乐值为该子矩阵上的所有数字的异或和。一组数字 a1,a2,...,an 的异或和为 a1 xor a2 xor ... xor an。（其中 xor 表示按位异或运算）
现在问你，该矩阵的所有子矩阵的快乐值之和为多少？
3.2 输入格式
从文件
matrix.in中读取数据。第一行两个整数 n,m。
接下来 n 行，每行 m 个整数，表示该矩阵。3.3 输出格式
输出到文件
matrix.out中。一行一个整数，表示答案。
3.4 输入样例
3.5 输出样例
5 4 // // 3 2 1 2 3 3 5 5 8 7 3 6 1 1 1 1 2 3 9 9 3.6 数据描述
822 总共 20 个测试点：
对于测试点 1∼4: 1≤n,m≤10,0≤gi,j<2^10 对于测试点 5∼6: 1≤n,m≤300,gi,j=1 对于测试点 7∼12: 1≤n,m≤300,0≤gi,j≤1 对于测试点 13∼20: 1≤n,m≤300,0≤gi,j<2^10 二位前缀异或和+按位高精度
20分代码
#include<bits/stdc++.h> using namespace std; long long n,m,a[305][305],b[305][305],cnt=0,x[305],xo[305]; int main(){//freopen("matrix.in","r",stdin);//freopen("matrix.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%lld",&a[i][j]);b[i][j]=a[i][j]^b[i-1][j]^b[i][j-1]^b[i-1][j-1]; }}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int x=i;x<=n;x++){for(int y=j;y<=m;y++){cnt+=(b[x][y]^b[i][j]^b[i][y-1]^b[x-1][j]);}}}}cout<<cnt;fclose(stdin);fclose(stdout);return 0; }AC代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[305][305],b[305][305],cnt=0,x[305],xo[305];
int main(){freopen("matrix.in","r",stdin);freopen("matrix.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%lld",&a[i][j]);}}for(int s=1;s<=n;s++){memset(x,0,sizeof(x));for(long long e=s;e<=n;e++){for(long long j=1;j<=m;j++){x[j]=a[e][j]^x[j];//位运算xo[j]=xo[j-1]^x[j];}for(long long i=0;i<10;i++){long long cnt0=1,cnt1=0;for(long long k=1;k<=m;k++){//按位求权值if(xo[k]&(1<<i)){cnt+=1ll*(1<<i)*cnt0;cnt1++;}else{cnt+=1ll*(1<<i)*cnt1;cnt0++;}}}}}cout<<cnt;fclose(stdin);fclose(stdout);return 0;
} //时间复杂度O(n^2 m)
原神，启动
4.1 问题描述
给你一个长度为 n 的数列 a1,a2,...,an。
再给你一个长度为 m 的数列 b1,b2,...,bm。
现在再再再给你一个正整数 p，让你生成一个长度为 n×m 的数列 c1,c2,...,cn×m。
其中满足 c(i−1)×m+j=(ai+bj) mod p。
现在问你数列 c 中有多少个数对 (i,j) 满足 i<j 且 ci>cj？4.2 输入格式
从文件
pair.in中读取数据。第一行两个整数 n,m,p。
第二行 nn 个整数，表示 a1∼an。
第三行 mm 个整数，表示 b1∼bm。4.3 输出格式
输出到文件
pair.out中。一行一个整数，表示答案。
4.4 输入样例
6 7 10 // // // // 1 1 4 5 1 4 // 1 9 1 9 8 1 0 4.5 输出样例
294 4.6 数据描述
总共 20 个测试点：
对于测试点 1∼4: 1≤n,m≤100,1≤p≤10,0≤ai,bi<p 对于测试点 5∼6: 1≤n,m≤1000,1≤p≤10,0≤ai,bi<p 对于测试点 7∼8: 1≤n,m≤1000000,p=2,0≤ai,bi<p 对于测试点 9∼20: 1≤n,m≤1000000,1≤p≤10,0≤ai,bi<p
30分代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,p,a[1000006],b[1000006],cnt=0;
long long c[10000007];
int main(){freopen("pair.in","r",stdin);freopen("pair.out","w",stdout);cin>>n>>m>>p;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++)scanf("%d",&b[i]);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){c[(i-1)*m+j]=(a[i]+b[j])%p;}}for(int i=1;i<n*m;i++){for(int j=i+1;j<=n*m;j++){if(c[i]>c[j]){cnt++;} }}cout<<cnt;fclose(stdin);fclose(stdout);return 0;
}
因为p<=10，所以可以高精度+分部讨论。
理论存在，魔法开始！！！
AC代码
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+5, M=1e6+5; bool flag=0;//特殊样例全0 int n, m, p, a[M], b[M]; ll num[10], numb[M], nixu[10];//nixu[i]表示b数组+i之后的逆序对个数 ll ans[200], cnt=0; void jia(ll k){ans[0]+=k;int pos=0;while(1){if(ans[pos]>=1000000){//压位高精，一个变量存6位，不再存1位ans[pos+1]+=ans[pos]/1000000;ans[pos]%=1000000;if(++pos>cnt){cnt++;}}else break;} } int main(){cin >> n >> m >> p;for(int i=1; i<=n; i++) {cin >> a[i];if(a[i]!=0) flag=1;}for(int i=1; i<=m; i++){cin >> b[i];if(b[i]!=0) flag=1;numb[b[i]]++;}//预处理,nixu[i]存储a[i]加到b[1]~b[m]各个数上的逆序对数for(int j=0; j<p; j++){//a、b数组范围在0~9，打表预处理,memset(num, 0, sizeof num);for(int i=1; i<=m; i++){//枚举bfor(int k=b[i]+1; k<p; k++){//k=b[(i+j)%p]+1;//保证数字比b[i]大nixu[j] += num[k];}num[b[i]]++;//num[(i+j)%p]++;//记录b[i]次数，为下次循环准备b[i]=(b[i]+1)%p;//注释掉//保证自增，代替掉模拟a[i]+b[j]的枚举，因为a、b数组元素皆<p}}memset(num, 0, sizeof num);//ll ans=0;for(int i=1; i<=n; i++){//ans+=nixu[a[i]];//块内的逆序对数量,c[(i-1)%m+1]~c[(i-1)*m+m]jia(nixu[a[i]]);for(int j=0; j<p; j++){int x=(j+a[i])%p;//某一个c的值for(int k=x+1; k<p; k++){//ans+=1ll*numb[j]*num[k];//块与块之间的个数（nm太大只能求块与块加、间的），不做优化30ll x=1ll*numb[j]*num[k];jia(x);}}for(int j=0; j<p; j++){num[(j+a[i])%p]+=numb[j];}}if(!flag) cout << 0;else{cout << ans[cnt];for(int i=cnt-1; i>=0; i--){printf("%06lld", ans[i]);}}return 0; }
你要AKIOI吗？？？
《孤勇者》 by：leecholas
都是勇敢的 你屏上的RE 你的 不同 你犯的错
都不必隐藏 你破旧的草稿 你的 代码 你的自傲
他们说 要带着光 驯服每一个 WA
他们说 要缝好你的伤 而代价是抄袭
为何孤独 不可 光荣
人只有不完美 值得歌颂
谁说轮轮WA的不算英雄
爱你孤身走考场 爱你坚持的模样
爱你对峙过 NOI
不肯哭一场
爱你和我那么像
AC是幻想？
去吗？配吗？以最菜的技术
战吗？战啊！以最卑微的梦
致那机房中的呜咽与怒吼
谁说天天AC的才算英雄
他们说要戒了你的狂 就像擦掉了答辩
他们说要拿到数据点 而代价是抄袭
那就让我 不可 阻挡
你一样骄傲着 那种孤勇
谁说次次 TLE 不算英雄
爱你孤身走考场 爱你坚持的模样
爱你对峙过 NOI
不肯哭一场
爱你最菜的编译
却敢压最凶的题
爱你和我那么像
AC是幻想？
去吗？配吗？以最菜的技术
战吗？战啊！以最卑微的梦
致那机房中的呜咽与怒吼
谁说天天AK的才算英雄
你的斑驳 与众不同
你的沉默 震耳欲聋
爱你孤身走考场 爱你坚持的模样 爱你对峙过 NOI
不肯哭一场
你将你行行代码
在记录之上
去吗？去啊！以卑微的技术
战吗？战啊！以孤高的性格
致那机房中的呜咽与怒吼
谁说天天AC的才算英雄
