信息学奥赛-入门级 题库
数字游戏
【问题描述】
小K同学向小P同学发送了一个长度为8的 01字符串来玩数字游戏,小P 同学想 要知道字符串中究竟有多少个1。
注意:01字符串为每一个字符是0或者1的字符串,如“101”(不含双引号)为一 个长度为3的01字符串。
【输入格式】
输入文件名为number in。
输入文件只有一行, 一个长度为8的01字符串s。
【输出格式】
输出文件名为number.out。
输出文件只有一行,包含一个整数,即01字符串中字符1 的个数。
【输入输出样例1】

【输入输出样例1说明】
该01字符串中有2个字符1。
【输入输出样例2】

【输入输出样例2说明】
该01字符串中有8个字符1。
【数据规模与约定】
对于20%的数据,保证输入的字符全部为0。
对于100%的数据,输入只可能包含字符0和字符1,字符串长度固定为8。
#include<bits/stdc++.h>
using namespace std;
string str;
int cnt = 0;
int main(){
cin >> str;
for(int i = 0;str[i];i++) if(str[i] == '1') cnt++;
cout << cnt << endl;
return 0;
}
公交换乘
【问题描述】
著名旅游城市B市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交 车的优惠方案:
1.在搭乘一次地铁后可以获得一张优惠票,有效期为45分钟,在有效期内可以 消耗这张优惠票,免费搭乘一次票价不超过地铁票价的公交车。在有效期内指 开始乘公交车的时间与开始乘地铁的时间之差小于等于45分钟,即:tbus-tsubway≤45
2. 搭乘地铁获得的优惠票可以累积,即可以连续搭乘若干次地铁后再连续使用优 惠票搭乘公交车。
3. 搭乘公交车时,如果可以使用优惠票一定会使用优惠票;如果有多张优惠票满 足条件,则优先消耗获得最早的优惠票。
现在你得到了小轩最近的公共交通出行记录,你能帮他算算他的花费吗?
【输入格式】
输入文件名为transfer . in。
输入文件的第一行包含一个正整数n,代表乘车记录的数量。
接下来的n行,每行包含3个整数,相邻两数之间以一个空格分隔。第i行的 第1个整数代表第i条记录乘坐的交通工具,0代表地铁,1代表公交车;第2个 整数代表第i条记录乘车的票价pricei;第三个整数代表第i条记录开始乘车的时 间ti (距0时刻的分钟数)。
我们保证出行记录是按照开始乘车的时间顺序给出的,且不会有两次乘车记录出现 在同一分钟。
【输出格式】
输出文件名为transfer . out。
输出文件有一行,包含一个正整数,代表小轩出行的总花费
【 输入输出样例 1】

【输入输出样例1说明】
第一条记录,在第3分钟花费10元乘坐地铁。
第二条记录,在第46分钟乘坐公交车,可以使用第一条记录中乘坐地铁获得的优 惠票,因此没有花费。
第三条记录,在第50分种花费12元乘坐地铁。
第四条记录,在第96分钟乘坐公交车,由于距离第三条记录中乘坐地铁已超过45 分钟,所以优惠票已失效,花费3元乘坐公交车。
第五条记录,在第110分钟花费5元乘坐地铁。
第六条记录,在第135分钟乘坐公交车,由于此时手中只有第五条记录中乘坐地铁 获得的优惠票有效,而本次公交车的票价为6元,高于第五条记录中地铁的票价5元, 所以不能使用优惠票,花费6元乘坐公交车。
总共花费36元。
【输入输出样例2】

【输入输出样例2说明】
第一条记录,在第1分钟花费5元乘坐地铁。
第二条记录,在第16分钟花费20元乘坐地铁。
第三条记录,在第23分钟花费7元乘坐地铁。
第四条记录,在第31分钟乘坐公交车,此时只有第二条记录中乘坐的地铁票价高 于本次公交车票价,所以使用第二条记录中乘坐地铁获得的优惠票。
第五条记录,在第38分钟乘坐公交车,此时第一条和第三条记录中乘坐地铁获得 的优惠票都可以使用,使用获得最早的优惠票,即第一条记录中乘坐地铁获得的优惠票。
第六条记录,在第68分钟乘坐公交车,使用第三条记录中乘坐地铁获得的优惠票。 总共花费32元。
【数据规模与约定】

#include<bits/stdc++.h>
using namespace std;
int n,opt,m,t,num=0,ans=0;
struct data {
int m,t;
bool ok;
} p[100001];
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d%d%d",&opt,&m,&t);
if(opt==0) {
num++;
p[num].m=m;
p[num].t=t;
p[num].ok=0;
ans+=m;
}
if(opt==1) {
bool ok=0;
for(int j=1; j<=num; j++) {
if(t-p[j].t<=45&&p[j].ok==0&&m<=p[j].m) {
p[j].ok=1;
ok=1;
break;
}
}
if(ok==0)
ans+=m;
}
}
printf("%d\n",ans);
return 0;
}
纪念品
【问题描述】
小伟突然获得一种超能力,他知道未来T天N种纪念品每天的价格。某个纪念品 的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。
每天,小伟可以进行以下两种交易无限次:
1. 任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;
2. 卖出持有的任意一个纪念品,以当日价格换回金币。
每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当 日卖出换回金币。当然, 一直持有纪念品也是可以的。
T天之后,小伟的超能力消失。因此他一定会在第T天卖出所有纪念品换回金币。 小伟现在有M枚金币,他想要在超能力消失后拥有尽可能多的金币。
【输入格式】
输入文件名为souvenir . in。
第一行包含三个正整数T,N,M,相邻两数之间以一个空格分开,分别代表未来天数 T,纪念品数量N,小伟现在拥有的金币数量M。
接下来T行,每行包含N个正整数,相邻两数之间以一个空格分隔。第i行的N个正整数分别为Pi1,Pi2, …… ,Pin,其中Pi,j表示第i天第j种纪念品的价格。
【输出格式】
输出文件名为souvenir . out。
输出仅一行,包含一个正整数,表示小伟在超能力消失后最多能拥有的金币数量。
【输入输出样例1】

【 输入输出样例1说明】
最佳策略是:
第二天花光所有100枚金币买入5个纪念品1;
第三天卖出5个纪念品1,获得金币125枚;
第四天买入6个纪念品1,剩余5枚金币;
第六天必须卖出所有纪念品换回300枚金币,第四天剩余5枚金币,共305枚金币。
超能力消失后,小伟最多拥有305枚金币。
【输入输出样例2】

【输入输出样例2说明】
最佳策略是:
第一天花光所有金币买入10个纪念品1;
第二天卖出全部纪念品1得到150枚金币并买入8个纪念品2和1个纪念品3,剩 余1枚金币;
第三天必须卖出所有纪念品换回216枚金币,第二天剩余1枚金币,共217枚金币。 超能力消失后,小伟最多拥有217枚金币。
【数据规模与约定】
对于10%的数据,T=1。
对于30%的数据,T≤4,N≤4,M≤100,所有价格10≤Pij≤100。
另有15%的数据,T≤100,N=1。
另有15%的数据,T=2,N≤100。
对于100%的数据,T≤100,N≤100,M≤
,所有价格1≤Pij≤10⁴,数 据保证任意时刻,小明手上的金币数不可能超过10⁴。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2+10;
const int M = 1e4+10;
int t,n,m;
int val[N][N];
int f[N]; //第 x 天最多有多少钱
int tmp[M],mx;
void solve(){
f[1] = m;
for(int day = 2;day <= t;day++){
for(int i = 1;i < day;i++){
memset(tmp,0,sizeof tmp); mx = m;
for(int j = 1;j <= n;j++){
for(int v = val[i][j]; v <= f[i];v++){
tmp[v] = max(tmp[v-val[i][j]]+val[day][j],tmp[v]);
mx = max(mx,tmp[v]+f[i]-v);
}
}
f[day] = max(f[day],mx);
}
f[day] = max(f[day],f[day-1]);
}
//for(int i = 1;i <= t;i++) printf("%d\n",f[i]);
printf("%d\n",f[t]);
}
int main(){
scanf("%d%d%d",&t,&n,&m);
for(int i = 1;i <= t;i++)
for(int j = 1;j <= n;j++) scanf("%d",&val[i][j]);
solve();
return 0;
}
加工零件
【问题描述】
凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很 神奇。工厂里有n位工人,工人们从1~n编号。某些工人之间存在双向的零件传送 带。保证每两名工人之间最多只存在一条传送带。
如果x号工人想生产一个被加工到第L(L>1)阶段的零件,则所有 与 x 号 工 人 有传送带直接相连的工人,都需要生产一个被加工到第L- 1阶段的零件(但x号工 人自己无需生产第L - 1阶段的零件)。
如果x号工人想生产一个被加工到第1阶段的零件,则所有与x号工人有传送带直接 相连的工人,都需要为x号工人提供一个原材料。
轩 轩 是 1 号工人。现在给出q张工单,第i张工单表示编号为ai的工人想生产 一个第Li阶段的零件。轩轩想知道对于每张工单,他是否需要给别人提供原材料。他 知道聪明的你一定可以帮他计算出来!
【输入格式】
输入文件名为work.in。
第一行两个正整数n,m和q,分别表示工人的数目、传送带的数目和工单的数目。
接下来m行,每行两个正整数u和v,表示编号为u和v的工人之间存在 一条零 件传输带。保证u≠v。
接下来q行,每行两个正整数a和L,表示编号为a的工人想生产 一个第L阶段 的零件。
【输出格式】
输出文件名为work . out。
共q行,每行一个字符串“Yes”或者“No”。如果按照第i张工单生产,需要编号为 1的轩轩提供原材料,则在第i行输出“Yes”;否则在第i行输出“No”。注意输出不含 引号。
【输入输出样例 1】

【输入输出样例1说明】

编号为1的工人想生产第1阶段的零件,需要编号为2的工人提供原材料。
编号为2的工人想生产第1阶段的零件,需要编号为1和3的工人提供原材料。
编号为3的工人想生产第1阶段的零件,需要编号为2的工人提供原材料。
编号为1的工人想生产第2阶段的零件,需要编号为2的工人生产第1阶段的零 件,需要编号为1和3的工人提供原材料。
编号为2的工人想生产第2阶段的零件,需要编号为1和3的工人生产第1阶段 的零件,他/她们都需要编号为2的工人提供原材料。
编号为3的工人想生产第2阶段的零件,需要编号为2的工人生产第1阶段的零件,需要编号为1和3的工人提供原材料。
【输入输出样例2】

【输入输出样例2说明】

编号为1的工人想生产第1阶段的零件,需要编号为2和5的工人提供原材料。
编号为1的工人想生产第2阶段的零件,需要编号为2和5的工人生产第1阶段 的零件,需要编号为1,3,4 的工人提供原材料。
编号为1的工人想生产第3阶段的零件,需要编号为2和5的工人生产第2阶段的零件,需要编号为1,3,4的工人生产第1阶段的零件,需要编号为2,3,4,5 的工人提供 原材料。
编号为1的工人想生产第4阶段的零件,需要编号为2和5的工人生产第3阶段 的零件,需要编号为1,3,4的工人生产第2阶段的零件,需要编号为2,3,4,5 的工人生产 第1阶段的零件,需要全部工人提供原材料。
编号为1的工人想生产第5阶段的零件,需要编号为2和5的工人生产第4阶段 的零件,需要编号为1,3,4的工人生产第3阶段的零件,需要编号为2,3,4,5 的工人生产 第2阶段的零件,需要全部工人生产第1阶段的零件,需要全部工人提供原材料。
【数据规模与约定】
共20个测试点。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 2*N;
typedef long long ll;
int n,m,q;
int head[N],edge[M],ver[M],nex[M] ,tot = 1;
void addEdge(int x,int y,int z){
ver[++tot] = y; edge[tot] = z;
nex[tot] = head[x]; head[x] = tot;
}
int getInt(){
int res = 0;
bool neg = false;
char c = getchar();
while(c != '-' && (c < '0' || c > '9')) c = getchar();
if(c == '-') neg = true, c = getchar();
while(c >= '0' && c <= '9') res = res*10+c-'0',c = getchar();
return neg?-res:res;
}
queue<int> que;
int dis[N],vis[N];
bool solve(int a,int l){
if(dis[a] <= l && !((dis[a]&1) ^ (l&1))) return true;
if(dis[a+n] <= l && !((dis[a+n]&1) ^ (l&1))) return true;
return false;
}
void SPFA(int s){
que.push(s);
memset(dis,0x3f,sizeof dis);
dis[s] = 0;
while(que.size()){
int x = que.front(); que.pop();
vis[x] = false;
for(int i = head[x];i ;i = nex[i]){
int y = ver[i], z = edge[i];
if(dis[y] > dis[x]+z){
dis[y] = dis[x]+z;
if(!vis[y]) que.push(y),vis[y] = true;
}
}
}
}
int main(){
n = getInt(); m = getInt(); q = getInt();
for(int i = 1,x,y;i <= m;i++){
x = getInt(); y = getInt();
addEdge(x,y+n,1); addEdge(y+n,x,1);
addEdge(x+n,y,1); addEdge(y,x+n,1);
}
SPFA(1);
//for(int i = 1;i <= n<<1;i++) cout << dis[i] << endl;
for(int i = 1,a,l;i <= q;i++){
a = getInt(); l = getInt();
if(solve(a,l)) puts("Yes");
else puts("No");
}
return 0;
}
#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main() {
scanf("%s", st);
int n = strlen(st);
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
char c = st[i - 1];
if (c >= 'a')
st[i - 1] = c - 'a' + 'A';
}
}
printf("%s", st);
return 0;
}
#include<cstdio>
using namespace std;
int n, m;
int a[100], b[100];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
a[i] = b[i] = 0;
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d%d", &x, &y);
if (a[x] < y && b[y] < x) {
if (a[x] > 0)
b[a[x]] = 0;
if (b[y] > 0)
a[b[y]] = 0;
a[x] = y;
b[y] = x;
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] == 0)
++ans;
if (b[i] == 0)
++ans;
}
printf("%d", ans);
return 0;
}
假设输入的n和m都是正整数,x和y都是在[1, n]的范围内的整数,完成下 面的判断题和单选题:
#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {
if (l > r)
return 0;
int min = maxn, mink;
for (int i = l; i <= r; ++i) {
if (min > a[i]) {
min = a[i];
mink = i;
}
}
int lres = f(l, mink - 1, depth + 1);
int rres = f(mink + 1, r, depth + 1);
return lres + rres + depth * b[mink];
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> b[i];
cout << f(0, n - 1, 1) << endl;
return 0;
}
(矩阵变幻)有一个奇幻的矩阵,在不停的变幻,其变幻方式为:数字0变成 矩阵
0 0
0 1
数字1变成矩阵
1 1
1 0
最初该矩阵只有一个元素0,变幻n次后,矩阵会变成什么样?
例如,矩阵最初为:[0]:矩阵变幻1次后:
0 0
0 1
矩阵变幻2次后:
0 0 0 0
0 1 0 1
0 0 1 1
0 1 1 0
输入一行一个不超过10的正整数n输出变幻n次后的矩阵。试补全程序。
提示:
“«” 表示二进制左移运算符,例如(11)_2 «2 = (1100)_2(11)2«2=(1100)2;而“^”表示二进制异或运算符,它将两个参与运算的数中的每个对应的二进制 位一进行比较,若两个二进制位相同,则运算结果的对应二进制位为0 ,反之 为1。
#include <cstdio>
using namespace std;
int n;
const int max_size = 1<<10;
int res[max_size][max_size];
void recursive(int x, int y, int n,int t){
if(n==0){
res[x][y]= ① ;
return ;
}
int step = 1<< (n-1);
recursive( ②,n-1,t);
recursive(x,y+step,n-1,t);
recursive(x+step,y,n-1,t);
recursive( ③ ,n-1,!t);
}
int main(){
scanf("%d",&n);
recursive(0,0,④ );
int size = ⑤;
for(int i=0;i<size;i++){
for(int j=0;j<size;j++)
printf("%d",res[i][j]);
puts(" ");
}
return 0;
}
(计数排序)计数排序是一个广泛使用的排序方法。下面的程序使用双关键字 计数排序,将n对10000以内的整数,从小到大排序。
例如有三对整数(3, 4) (3, 4)、(2, 4) (2, 4)、(3, 3) (3, 3),那么排序之后应该是 (2, 4) (2, 4)、(3, 3) (3, 3)、(3, 4) (3, 4)。
输入第一行为nn接下来nn行,第ii行有两个数a[i]a[i]和b[i]b[i]分别表 示第ii对整数的第一关键字和第二关键字。
从小到大排序后输出。
数据范围

提示:应先对第二关键字排序,再对第一关键字排序。数组。ord[ ]存储第二关键 字排序的结果,数组res[ ]存储双关键字排序的结果。
试补全程序。
#include <cstdio>
#include <cstring> using namespace std; const int maxn = 10000000; const int maxs = 10000;
int n; unsigned a[maxn], b[maxn],res[maxn], ord[maxn]; unsigned
cnt[maxs + 1]; int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d%d", &a[i], &b[i]);
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i)
①; // 利用 cnt 数组统计数量
for (int i = 0; i < maxs; ++i)
cnt[i + 1] += cnt[i];
for (int i = 0; i < n; ++i)
②; // 记录初步排序结果
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i)
③; // 利用 cnt 数组统计数量
for (int i = 0; i < maxs; ++i)
cnt[i + 1] += cnt[i];
for (int i = n - 1; i >= 0; --i)
④ // 记录最终排序结果
for (int i = 0; i < n; i++)
printf("%d %d", ⑤);
return 0; }
买铅笔 (pencil)
【问题描述】
P 老师需要去商店买 n 支铅笔作为小朋友们参加NOIP 的礼物。她发现商店一共有 3 种包装的铅笔,不同包装内的铅笔数量有可能不同,价格也有可能不同。为了公平起 见,P 老师决定只买同一种包装的铅笔。
商店不允许将铅笔的包装拆开,因此P老师可能需要购买超过 n 支铅笔才够给小朋 友们发礼物。
现在P 老师想知道,在商店每种包装的数量都足够的情况下,要买够至少n 支铅 笔最少需要花费多少钱。
【输入格式】
从文件pencil.in 中读入数据。
输入的第一行包含一个正整数n ,表示需要的铅笔数量。
接下来三行,每行用两个正整数描述一种包装的铅笔:其中第一个整数表示这种 包装内铅笔的数量,第二个整数表示这种包装的价格。
保证所有的 7 个数都是不超过 10000 的正整数。
【输出格式】
输出到文件pencil.out 中。
输出一行一个整数,表示P 老师最少需要花费的钱。
【样例1输入】
57
2 2
50 30
30 27
【样例1输出】
54
【样例1说明】
铅笔的三种包装分别是:
● 2 支装,价格为 2 ;
● 50 支装,价格为 30 ;
● 30 支装,价格为 27 。
P老师需要购买至少57 支铅笔。
如果她选择购买第一种包装,那么她需要购买 29 份,共计 2 × 29 = 58 支,需要花 费的钱为 2 × 29 = 58 。
实际上,P老师会选择购买第三种包装,这样需要买 2 份。 虽然最后买到的铅笔数 量更多了,为 30 × 2 = 60 支,但花费却减少为 27 × 2 = 54 ,比第一种少。
对于第二种包装,虽然每支铅笔的价格是最低的,但要够发必须买 2 份,实际的 花费达到了 30 × 2 = 60 ,因此P老师也不会选择。
所以最后输出的答案是 54 。
【样例2输入】
9998
128 233
128 2333
128 666
【样例2输出】
18407
【样例3输入】
9999
101 1111
1 9999
1111 9999
【样例3输出】
89991
【子任务】
子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难,可以尝试 只解决一部分测试数据。
每个测试点的数据规模及特点如下表:

上表中“整倍数”的意义为:若为“√” ,表示对应数据所需要的铅笔数量 n 一定是每 种包装铅笔数量的整倍数 (这意味着一定可以不用多买铅笔)。
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int want, pcl[3], prc[3], sum = 1; //pcl 为三种铅笔的个数,prc 为三种铅笔的价格
cin >> want >> pcl[0] >> prc[0] >> pcl[1] >> prc[1] >> pcl[2] >> prc[2];
for(int i = 0; i < 3; i++){ //遍历三种铅笔
while(pcl[i]*sum < want) sum++; //循环求出 sum,即最小购买的包数
prc[i] *= sum; //求出每种铅笔的最终花费
sum = 1; //sum 重置
}
sort(prc,prc+3); //将三个花费排序,得到最小花费
cout << prc[0];
return 0;
}
回文日期 (date)
【问题描述】
在日常生活中,通过年、月、 日这三个要素可以表示出一个唯一确定的日期。
牛牛习惯用 8 位数字表示一个日期,其中,前 4 位代表年份,接下来 2 位代表月 份,最后 2 位代表日期。 显然:一个日期只有一种表示方法,而两个不同的日期的表 示方法不会相同。
牛牛认为,一个日期是回文的,当且仅当表示这个日期的 8 位数字是回文的。现 在,牛牛想知道:在他指定的两个日期之间 (包含这两个日期本身),有多少个真实存 在的日期是回文的。
【提示】
一个8位数字是回文的,当且仅当对于所有的 i
从左向右数的第 i 个 数字和第 9 - i 个数字 (即从右向左数的第i 个数字) 是相同的。
例如:
● 对于 2016 年 11 月 19 日,用8位数字 20161119 表示,它不是回文的。
● 对于 2010 年 1 月 2 日,用 8 位数字 20100102 表示,它是回文的。
● 对于 2010 年 10 月 2 日,用 8 位数字 20101002 表示,它不是回文的。
每一年中都有 12 个月份:
其中, 1 、 3 、 5 、 7 、 8 、 10 、 12 月每个月有 31 天; 4 、 6 、 9 、 11 月每个 月有30 天;而对于 2 月,闰年时有 29 天,平年时有 28 天。
一个年份是闰年当且仅当它满足下列两种情况其中的一种:
1. 这个年份是 4 的整数倍,但不是 100 的整数倍;
2. 这个年份是 400 的整数倍。 例如:
● 以下几个年份都是闰年: 2000 、 2012 、 2016 。
● 以下几个年份是平年: 1900 、 2011 、 2014 。
【输入格式】
从文件date.in 中读入数据。
输入包括两行,每行包括一个 8 位数字。
第一行表示牛牛指定的起始日期date1 。
第二行表示牛牛指定的终止日期date2 。
保证 date1 和 date2 都是真实存在的日期,且年份部分一定为 4 位数字,且首位数 字不为 0 。
保证 date1 一定不晚于 date2 。
【输出格式】
输出到文件date.out 中。
输出一行,包含一个整数,表示在 date1 和 date2 之间,有多少个日期是回文的。
【样例1输入】
20110101
20111231
【样例1输出】
1
【样例2输入】
20000101
20101231
【样例2输出】
2
【样例说明】
对于样例1 ,符合条件的日期是 20111102 。
对于样例2 ,符合条件的日期是 20011002 和 20100102 。
【子任务】
对于 60% 的数据,满足 date1 = date2 。
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int i,j,n,m,a,b,c,sum,ans;
int s[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=12;i++)
{
for(j=1;j<=s[i];j++)
{
c=(j%10)*1000+(j/10)*100+(i%10)*10+(i/10);
sum=c*10000+i*100+j;
if (sum<n||sum>m)
continue;
ans++;
}
}
printf("%d",ans);
return 0;
}
海港 (port)
【问题描述】
小K是一个海港的海关工作人员,每天都有许多船只到达海港,船上通常有很多来 自不同国家的乘客。
小K对这些到达海港的船只非常感兴趣,他按照时间记录下了到达海港的每一艘船 只情况;对于第 i 艘到达的船,他记录了这艘船到达的时间 ti (单位:秒),船上的乘 客数量 ki ,以及每名乘客的国籍 xi, 1 , xi,2 , . . . , xi,ki 。
小K统计了n 艘船的信息,希望你帮忙计算出以每一艘船到达时间为止的 24 小时 ( 24 小时 = 86400 秒) 内所有乘船到达的乘客来自多少个不同的国家。
形式化地讲,你需要计算 n 条信息。 对于输出的第 i 条信息,你需要统计满足
的船只p ,在所有的 xp,j 中,总共有多少个不同的数。
【输入格式】
从文件port.in 中读入数据。
第一行输入一个正整数n ,表示小K统计了n 艘船的信息。
接下来 n 行,每行描述一艘船的信息:前两个整数 ti 和 ki 分别表示这艘船到达海 港的时间和船上的乘客数量,接下来 ki 个整数 xi,j 表示船上乘客的国籍。
保证输入的ti 是递增的,单位是秒;表示从小K第一次上班开始计时,这艘船在第 ti 秒到达海港。

【输出格式】
输出到文件port.out 中。
输出n 行,第 i 行输出一个整数表示第i 艘船到达后的统计信息。
【样例1输入】
3
1 4 4 1 2 2
2 2 2 3
10 1 3
【样例1输出】
3
4
4
【样例1说明】
第一艘船在第 1 秒到达海港,最近 24 小时到达的船是第一艘船,共有 4 个乘客, 分别是来自国家 4, 1, 2, 2 ,共来自 3 个不同的国家;
第二艘船在第 2 秒到达海港,最近 24 小时到达的船是第一艘船和第二艘船,共有 4 + 2 = 6 个乘客,分别是来自国家 4, 1, 2, 2, 2, 3 ,共来自4 个不同的国家;
第三艘船在第 10 秒到达海港,最近 24 小时到达的船是第一艘船、第二艘船和第 三艘船,共有 4 + 2 + 1 = 7 个乘客,分别是来自国家 4, 1, 2, 2, 2, 3, 3 ,共来自4 个不同 的国家。
【样例2输入】
4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5
【样例2输出】
3
3
3
4
【样例2说明】
第一艘船在第 1 秒到达海港,最近 24 小时到达的船是第一艘船,共有 4 个乘客, 分别是来自国家 1, 2, 2, 3 ,共来自 3 个不同的国家;
第二艘船在第 3 秒到达海港,最近 24 小时到达的船是第一艘船和第二艘船,共有 4 + 2 = 6 个乘客,分别是来自国家 1, 2, 2, 3, 2, 3 ,共来自 3 个不同的国家;
第三艘船在第 86401 秒到达海港,最近 24 小时到达的船是第二艘船和第三艘船, 共有 2 + 2 = 4 个乘客,分别是来自国家 2, 3, 3, 4 ,共来自 3 个不同的国家;
第四艘船在第 86403 秒到达海港,最近 24 小时到达的船是第二艘船、第三艘船和 第四艘船,共有 2 + 2 + 1 = 5 个乘客,分别是来自国家 2, 3, 3, 4, 5 ,共来自4 个不同的 国家。

#include<iostream>
#include<queue>
using namespace std;
struct node
{
int t,c;
};
queue<node> q;
int a[100005];
int main()
{
int i,n,t,j,k,c,cnt=0;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>t>>k;
for(j=1;j<=k;j++)
{
cin>>c;
q.push(node({t,c}));
if(a[c]==0)
cnt++;
a[c]++;
}
while(q.back().t- q.front() .t>=86400)
{
if((--a[q.front().c ])==0)
cnt--;
q.pop();
}
cout<<cnt<<endl;
}
return 0;
}
魔法阵 (magic)
【问题描述】
六十年一次的魔法战争就要开始了,大魔法师准备从附近的魔法场中汲取魔法能 量。
大魔法师有 m 个魔法物品,编号分别为 1, 2, . . . , m 。每个物品具有一个魔法值,我 们用xi 表示编号为 i 的物品的魔法值。每个魔法值xi 是不超过n 的正整数,可能有多 个物品的魔法值相同。
大魔法师认为,当且仅当四个编号为a, b, c, d 的魔法物品满足 xa < xb < xc < xd , xb - xa = 2(xd - xc ) ,并且 xb - xa < (xc - xb ) ÷ 3 时,这四个魔法物品形成了一个魔法阵, 他称这四个魔法物品分别为这个魔法阵的A 物品,B 物品,C 物品,D 物品。
现在,大魔法师想要知道,对于每个魔法物品,作为某个魔法阵的A 物品出现的 次数,作为B物品的次数,作为C 物品的次数,和作为D 物品的次数。
【输入格式】
从文件magic.in 中读入数据。
输入文件的第一行包含两个空格隔开的正整数 n 和m 。
接下来 m 行,每行一个正整数,第 i + 1 行的正整数表示xi ,即编号为 i 的物品的 魔法值。
保证
每个 xi 是分别在合法范围内等概率 随机生成的。
【输出格式】
输出到文件magic.out 中。
共输出 m 行,每行四个整数。 第 i 行的四个整数依次表示编号为 i 的物品作 为A,B,C,D 物品分别出现的次数。
保证标准输出中的每个数都不会超过
每行相邻的两个数之间用恰好一个空格隔开。
【样例1输入】
30 8
1
24
7
28
5
29
26
24
【样例1输出】
4 0 0 0
0 0 1 0
0 2 0 0
0 0 1 1
1 3 0 0
0 0 0 2
0 0 2 2
0 0 1 0
【样例1说明】
共有 5 个魔法阵,分别为:
物品 1, 3, 7, 6 ,其魔法值分别为 1, 7, 26, 29 ;
物品 1, 5, 2, 7 ,其魔法值分别为 1, 5, 24, 26 ;
物品 1, 5, 7, 4 ,其魔法值分别为 1, 5, 26, 28 ;
物品 1, 5, 8, 7 ,其魔法值分别为 1, 5, 24, 26 ;
物品 5, 3, 4, 6 ,其魔法值分别为 5, 7, 28, 29 。
以物品 5 为例,它作为A 物品出现了 1 次,作为B物品出现了 3 次,没有作为C 物 品或者D 物品出现,所以这一行输出的四个数依次为 1, 3, 0, 0 。
此外,如果我们将输出看作一个 m 行 4 列的矩阵,那么每一列上的 m 个数之和都 应等于魔法阵的总数。所以,如果你的输出不满足这个性质,那么这个输出一定不正 确。你可以通过这个性质在一定程度上检查你的输出的正确性。
【样例2输入】
15 15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
【样例2输出】
5 0 0 0
4 0 0 0
3 5 0 0
2 4 0 0
1 3 0 0
0 2 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 0 1 0
0 0 2 1
0 0 3 2
0 0 4 3
0 0 5 4
0 0 0 5
【子任务】
每个测试点的详细数据范围见下表。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[40001];
int f[5][15001]/*作为第i个物品时,魔法值为j的次数*/;
int d[15001]/*魔法值为i的物品个数*/;
int sum=0,cnt=0;
int main(){
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);
d[a[i]]++;
}
for(int t=1;t*9+2<=n;t++){
sum=0;cnt=0;
for(int dd=9*t+2;dd<=n;dd++){
int cc=dd-t;//第三个物品
int bb=cc-6*t-1;//第二个物品
int aa=bb-2*t;//第一个物品
sum+=d[aa]*d[bb];//递推计算前缀和
f[3][cc]+=sum*d[dd];//魔法值为d的个数可能不是/不止1个
f[4][dd]+=sum*d[cc];//同理
}
for(int aa=n-9*t-1;aa>=1;aa--){
int bb=aa+2*t;//第二个物品
int cc=bb+6*t+1;//第三个物品
int dd=cc+t;//第四个物品
cnt+=d[cc]*d[dd];
f[1][aa]+=cnt*d[bb];
f[2][bb]+=cnt*d[aa];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=4;j++){
printf("%d ",f[j][a[i]]);
}
printf("\n");
}
return 0;
}
数字反转
【问题描述】
给定一个整数,请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形 式,即除非给定的原数为零,否则反转后得到的新数的最高位数字不应为零(参见样例2)。
【输入】
输入文件名为reverse.in。
输入共1行, 一个整数N。
【输出】
输出文件名为reverse.out。
输出共1行, 一个整数,表示反转后的新数。
【输入输出样例1】

【输入输出样例2】

【数据范围】
-1,000,000,000≤ N≤1,000,000,000。
#include<stdio.h>
int main(){
int m,i;
scanf("%d",&m);
if(m==0) printf("0");
if(m<0) {
m=-m;
printf("-");
}
do{
i=m%10;
m=m/10;
if(i!=0)printf("%d",i);
}while(i==0);
while(m!=0){
i=m%10;
m=m/10;
printf("%d",i);
}
return 0;
}
统计单词数
【问题描述】
一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位 置,有的还能统计出特定单词在文章中出现的次数。
现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章 中出现的次数和第一次出现的位置。 注意:匹配单词时,不区分大小写,但要求完全匹配, 即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同(参见样例1), 如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例2)。
【输入】
输入文件名为stat.in,2行。
第1行为一个字符串,其中只含字母,表示给定单词;
第2行为一个字符串,其中只可能包含字母和空格,表示给定的文章。
【输出】
输出文件名为stat .out。
只有一行,如果在文章中找到给定单词则输出两个整数,两个整数之间用一个空格隔开, 分别是单词在文章中出现的次数和第一次出现的位置(即在文章中第一次出现时,单词首字 母在文章中的位置,位置从0开始);如果单词在文章中没有出现,则直接输出一个整数- 1。
【输入输出样例1】

【输入输出样例1说明】
输出结果表示给定的单词To在文章中出现两次,第一 次出现的位置为0。
【输入输出样例2】

【输入输出样例2说明】
表示给定的单词to在文章中没有出现,输出整数- 1。
【 数据范围】
1≤单词长度≤10。
1≤文章长度≤1,000,000。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
char w[11],s[1000001]; //w为输入的单词,s为输入的文章
int j=0,x=0; //j用来遍历单词,x是表示状态的变量
//x为-1时,表示目前检测道德单词不是要输入的单词
//x为0时,表示遇到文章中的空格,准备开始下一个单词的检测
//x为1时,就是找到啦!
int oc,count=0,h=0; //oc用来储存第一个找到的位置
//count记录出现的次数,h用来确保oc只存储第一次找到的位置
gets(w);
gets(s); //最适合新手的输入方式
int a1,a2;
a1=strlen(w);
a2=strlen(s); //a1,a2分别是w,s的长度,strlen是系统自带函数
//注意,strlen函数很慢,务必事先把值存储到a1,a2中
//否则后几个测试点会出现TLE错误
for(int i=0;i<a1;i++) //遍历单词和文章,将其统一转换为小写
w[i]=tolower(w[i]);
for(int i=0;i<a2;i++) //tolower是系统自带函数
s[i]=tolower(s[i]); //相应变成大写的函数是toupper
for(int i=0;i<a2;i++) //遍历文章
{
j=0; //确保每次检测单词从第一个字母开始
if(w[j]==s[i]&&x==0) //x=0表示为空格状态,开始新单词的检测
//若第一个字母相同则进入下述判断流程
{
for(;j<a1;j++) //遍历单词
{
if(w[j]!=s[i+j]) //如果出现不同,x赋值为-1,退出循环
{
x=-1;
break;
}
x=-1; //如果一直一样,但后面还有单词,x赋值为-1
if(s[i+j+1]==' '||i+j+1==a2) //如果下一个是空格或者文章结束,则找到啦!
x=1;
}
if(x==1) //找到了后,要简单的储存一下
{
count++;
if(h==0)
oc=i;
h=1;
i=i+a1-1; //因为遍历的是单词,i没有变化,因此给i加上单词的长度
//注意,for循环有i++,因此要事先-1!
}
}
else if(s[i]==' ') //空格情况
x=0;
else //其他情况则为非相同的单词
x=-1;
}
if(count!=0) //如果找到了,按要求输出
cout << count << " " << oc;
else //没找到就输出-1
cout << "-1";
return 0;
}
瑞士轮
【背景】
在双人对决的竞技性比赛,如乒乓球、羽毛球、国际象棋中,最常见的赛制是淘汰赛和 循环赛。前者的特点是比赛场数少,每场都紧张刺激,但偶然性较高。后者的特点是较为公 平,偶然性较低,但比赛过程往往十分冗长。
本题中介绍的瑞士轮赛制,因最早使用于1895年在瑞士举办的国际象棋比赛而得名。 它可以看作是淘汰赛与循环赛的折衷,既保证了比赛的稳定性,又能使赛程不至于过长。
【问题描述】
2*N名编号为1~2N的选手共进行R轮比赛。每轮比赛开始前,以及所有比赛结束后, 都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已 参加过的所有比赛的得分和。总分相同的,约定编号较小的选手排名靠前。
每轮比赛的对阵安排与该轮比赛开始前的排名有关:第1 名 和 第 2 名 、 第 3 名 和 第 4 名、 … … 、第2K - 1名和第2K名、 … … 、第2N - 1名和第2N名,各进行 一 场比赛。每 场比赛胜者得1分,负者得0分。也就是说除了首轮以外,其它轮比赛的安排均不能事先确 定,而是要取决于选手在之前比赛中的表现。
现给定每个选手的初始分数及其实力值,试计算在R轮比赛过后,排名第Q的选手编号是多少。我们假设选手的实力值两两不同,且每场比赛中实力值较高的总能获胜。
【输入】
输入文件名为swiss .in。
输入的第一行是三个正整数N、R、Q,每两个数之间用一个空格隔开,表示有2*N名 选手、R轮比赛,以及我们关心的名次Q。
第二行是2*N个非负整数s1,s2,…,S2N,每两个数之间用一个空格隔开,其中si表示编 号为i的选手的初始分数。
第三行是2*N个正整数w1,w2,…,w2N,每两个数之间用一个空格隔开,其中wi表示编 号为i的选手的实力值。
【输出】
输出文件名为swiss . out。
输出只有一行,包含一个整数,即R轮比赛结束后,排名第Q的选手的编号。
【输入输出样例】

【输入输出样例说明】

【数据范围】
对于30%的数据,1≤N≤100;
对于50%的数据,1≤N≤10,000;
对于100% 的数据,1≤N≤100,000,1≤R≤50,1≤Q≤2N,0≤S1,S2, … ,S2N≤10⁸,l≤wi, w2, …,w2N≤10⁸。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxm = 2e5 + 10;
struct node
{
int id;
int score;
int power;
}stu[maxm],w[maxm],l[maxm];
bool cmp(node a,node b)
{
if (a.score==b.score)
return a.id < b.id;
return a.score > b.score;
}
bool cmp2(int s1,int s2,int id1,int id2)
{
if (s1==s2)
return id1 < id2;
return s1 > s2;
}
void merge(int ll,int rr)
{
int l1 = ll,l2 = ll,k = ll;
while (l1<=rr && l2<=rr)
if (cmp2(w[l1].score,l[l2].score,w[l1].id,l[l2].id))
stu[k++] = w[l1++];
else stu[k++] = l[l2++];
while (l1<=rr) stu[k++] = w[l1++];
while (l2<=rr) stu[k++] = l[l2++];
}
int main()
{
int n,r,q,i;
scanf("%d %d %d",&n,&r,&q);
for (i=1;i<=2*n;i++)
{
scanf("%d",&stu[i].score);
stu[i].id = i;
}
for (i=1;i<=2*n;i++)
scanf("%d",&stu[i].power);
sort(stu+1,stu+2*n+1,cmp);
while (r--)
{
int lo = 0,wi = 0;
for (i=1;i<=2*n;i+=2)
{
if (stu[i].power>stu[i+1].power)
{
w[++wi] = stu[i];
l[++lo] = stu[i+1];
w[wi].score++;
}
else
{
l[++lo] = stu[i];
w[++wi] = stu[i+1];
w[wi].score++;
}
}
merge(1,n);
}
printf("%d\n",stu[q].id);
return 0;
}
表达式的值
【问题描述】
对于1位二进制变量定义两种运算:

运算的优先级是:
1. 先计算括号内的,再计算括号外的。

现给定一个未完成的表达式,例如 +( * ),请你在横线处填入数字0或者1,请问有多少种填法可以使得表达式的值为0。
【输入】
输入文件名为exp.in,共2行。
第1行为一个整数L,表示给定的表达式中除去横线外{的运算符和括号的个数。
第2行为一个字符串包含L个字符,其中只包含’(’、’)’、²+’、”*这4种字符,其中’ (’、’)’是左右括号,’+’、’*’分别表示前面定义的运算符“田”和“×”。这行字符按顺序 给出了给定表达式中除去变量外的运算符和括号。
【输出】
输出文件exp.out共1行。包含一个整数,即所有的方案数。 注意:这个数可能会很大, 请输出方案数对10007取模后的结果。
【输入输出样例1】

【输入输出样例说明】
给定的表达式包括横线字符之后为: +( * )
在横线位置填入(0、0、0)、(0、1、0)、(0、0、1)时,表达式的值均为0,所以共有3 种填法。
【数据范围】
对于20%的数据有O≤L≤10。
对于50%的数据有O≤L≤1,000。
对于70%的数据有O≤L≤10,000。
对于100%的数据有O≤L≤100,000。
对于50%的数据输入表达式中不含括号。
#include <bits/stdc++.h>
using namespace std;
const int MOD=10007;
int f[2][100005]; //每一位是0的可能性和是1的可能性
int main()
{
int len;
string c,pol=".";
cin>>len>>c;
stack<char> sta;
for(int i=0;i<len;i++)
{
if(c[i]=='(' || c[i]=='*')
sta.push(c[i]);
if(c[i]=='+')
{
while(!sta.empty() && sta.top()=='*')
{
pol+=sta.top();
sta.pop();
}
sta.push('+');
}
if(c[i]==')')
{
while(sta.top()!='(')
{
pol+=sta.top();
sta.pop();
}
sta.pop();
}
if(c[i]!='(' && c[i]!=')')
pol+='.';
}
while(!sta.empty())
{
pol+=sta.top();
sta.pop();
}
int j=0;
for(int i=0;i<(int)pol.length();i++)
{
if(pol[i]=='.')
{
j++;
f[0][j]=1;
f[1][j]=1;
}
if(pol[i]=='*')
{
j--;
f[0][j]=(f[0][j+1]*f[1][j]+f[0][j]*f[1][j+1]+f[0][j]*f[0][j+1])%MOD;
f[1][j]=(f[1][j]*f[1][j+1])%MOD;
}
if(pol[i]=='+')
{
j--;
f[1][j]=(f[0][j]*f[1][j+1]+f[0][j+1]*f[1][j]+f[1][j]*f[1][j+1])%MOD;
f[0][j]=(f[0][j]*f[0][j+1])%MOD;
}
}
cout<<f[0][j]<<endl; //f[0][1]
return 0;
}
金币
【问题描述】
国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天(第七、八、九、十天),每天收到四枚金币……;这种工资发放模式会一直这样延续下去:当连续 N 天每天收到 N 枚金币后,骑士会在之后的连续 N+1 天里,每天收到 N+1 枚金币。
请计算在前 K 天里,骑士一共获得了多少金币。
【输入格式】
输入文件名为 coin.in。
输入文件只有 1 行,包含一个正整数 K,表示发放金币的天数。
【输出格式】
输出文件名为 coin.out。
输出文件只有 1 行,包含一个正整数,即骑士收到的金币数。
【输入输出样例 1】

【输入输出样例 1 说明】
骑士第一天收到一枚金币;第二天和第三天,每天收到两枚金币;第四、五、六天,每天收到三枚金币。因此一共收到 1+2+2+3+3+3=14 枚金币。
【输入输出样例 2】

【数据说明】
对于 100%的数据,1 ≤ K ≤ 10,000。
# include<stdio.h>
int main()
{
int m,n,k,s=0,count=1,flag=1;
scanf("%d",&k);
for(m=1;m<=k;count++,flag++){
for(n=1;n<=flag;n++){
s+=count;m++;
if(m>k) break;
}
}
printf("%d",s);
return 0;
}
扫雷游戏
【问题描述】
扫雷游戏是一款十分经典的单机小游戏。在 n 行 m 列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下,找出所有的非地雷格。
现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格周围的地雷格数。
注:一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。
【输入格式】
输入文件名为 mine.in。
输入文件第一行是用一个空格隔开的两个整数n和m,分别表示雷区的行数和列数。
接下来 n 行,每行 m 个字符,描述了雷区中的地雷分布情况。字符’*’表示相应格子是地雷格,字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。
【输出格式】
输出文件名为 mine.out。
输出文件包含 n 行,每行 m 个字符,描述整个雷区。用’*’表示地雷格,用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。
【输入输出样例 1】

【输入输出样例 2】

【数据说明】
对于 100%的数据,1≤n≤100,1≤m≤100。
#include <iostream>
using namespace std;
int main(){
int n,m,cnt=0;
char a[102][102];
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]!='*'){
if(a[i-1][j-1]=='*') cnt++;
if(a[i-1][j]=='*') cnt++;
if(a[i-1][j+1]=='*') cnt++;
if(a[i][j-1]=='*') cnt++;
if(a[i][j+1]=='*') cnt++;
if(a[i+1][j-1]=='*') cnt++;
if(a[i+1][j]=='*') cnt++;
if(a[i+1][j+1]=='*') cnt++;
cout<<cnt;
cnt=0;
}
else{
cout<<"*";
}
}
cout<<" "<<endl;
}
return 0;
}
求和
【问题描述】
一条狭长的纸带被均匀划分出了 n 个格子,格子编号从 1 到 n。每个格子上都染了一种颜色colori(用[1,m]当中的一个整数表示),并且写了一个数字numberi。

定义一种特殊的三元组:(x, y, z),其中 x,y,z 都代表纸带上格子的编号,这里的三元组要求满足以下两个条件:
x,y,z,都是整数, x< y < z, y − x = z − y
colorx =colorz
满足上述条件的三元组的分数规定为(x + z) * (numberx +numberz)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大,你只要输出整个纸带的分数除以 10,007 所得的余数即可。
【输入格式】
输入文件名为 sum.in。
第一行是用一个空格隔开的两个正整数n和m,n代表纸带上格子的个数,m代表纸带上颜色的种类数。
第二行有n个用空格隔开的正整数,第i个数字numberi代表纸带上编号为i的格子上面写的数字。
第三行有n个用空格隔开的正整数,第i个数字colori代表纸带上编号为i的格子染的颜色。
【输出格式】
输出文件名为 sum.out。
共一行,一个整数,表示所求的纸带分数除以 10,007 所得的余数。
【输入输出样例 1】

【输入输出样例 1 说明】
纸带如题目描述中的图所示。
所有满足条件的三元组为:(1, 3, 5), (4, 5, 6)。
所以纸带的分数为(1 + 5) *(5 + 2) + (4 + 6) * (2 + 2) = 42 + 40 = 82。
【输入输出样例 2】

【数据说明】
对于第 1 组至第 2 组数据,1 ≤ n ≤ 100, 1 ≤ m ≤ 5;
对于第 3 组至第 4 组数据,1 ≤ n ≤ 3000, 1 ≤ m ≤ 100;
对于第 5 组至第 6 组数据,1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000,且不存在出现次数超过 20 的颜色;
对于全部 10 组 数 据 , 1 ≤ n ≤ 100000, 1 ≤m ≤ 100000, 1 ≤colori ≤ m, 1 ≤numberi ≤ 100000。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxj = 1e5+100,mod = 10007;
int a[maxj],c[maxj],cnt[maxj][3],sum[maxj][3],x[maxj];
int32_t main(){//前缀和,颜色相同,等差数列,公式推导
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=n;++i){
cin>>c[i];
cnt[c[i]][i%2]++;
sum[c[i]][i%2]=(sum[c[i]][i%2]+a[i])%mod;
}
int ans=0;
for(int i = 1;i <=n;++i){
ans = (ans + i*(a[i]*(cnt[c[i]][i%2]-2)%mod+sum[c[i]][i%2]))%mod;
}
cout<< ans <<'\n';
return 0 ;
}