首先非常感谢各位同学的参加，还有出题验题同学的辛勤付出
昨天想偷懒就是不想再把我C++11的style改没了，大家看不懂的可以百度一下哦，懒得再写gcc了，毕竟代码是通的
//代表的是行注释，所以那个读入文件和输出到文件就不用问我啦
题目类型一览
A Kannyi的数字密码 (模拟&&复杂的循环||手算)
B Kannyi爱干净(注意变量初始化||set)
C Kannyi的正方体和圆柱体(输入输出签到，PI已提示)
D kannyi的独木桥(max和min)
E Kannyi的简单检查 (循环签到 注意'-')
F Kannyi的倒计时(a+b签到)
G kannyi的开矿规划(大力模拟)
H Kannyi的闯关游戏(BFS 两次最短路)
I Kannyi爱种树(线段相交)
J Kannyi 的easy problem((数学||瞎猜)&&长整型)
K Kannyi的复旦(二分||stl)
5619: Kannyi的数字密码 
总提交: 80 测试通过:30
描述
今天Kannyi说他要生成一些他的密码，他会选择Smith数作为他不同账号的密码。
Smith数是这样定义的：一个数的各位之和等于其所分解的素因子各位数字之和。例如378就是Smith数，因为378=2×3×3×3×7，而且3+7+8=2+3+3+3+7。在这个定义中，这些素因子也要拆成各位数字再求和，例如22=2*11，且2+2=2+1+1，所以22也是Smith数。现在要去掉质数，并将剩下的数重新命名为kannyi数。
现在给你一个a，请输出第a个Kannyi数。
输入
输入数据包含多组测试实例，每个测试实例占一行，为一个正整数a (1 ≤ a ≤ 30)。
输出
每个测试样例占一行，为第a个Kannyi数。
样例输入
3
样例输出
27
提示
OJ的评测机为windows，如需使用长整数(long long或__int64)，输入输出请使用%I64d，本次比赛不再提示。
这个题目应该还好吧，满足要求的数非常之少，甚至可以手算出来
当然你也可以去写这个循环，数位之和就是个进制转换
#include<bits/stdc++.h>
using namespace std;
//以上为c++11的万能头文件，十分方便好用
int sum_of_digit(int n)//把代码封装成函数，好用，好理解，减少代码冗余
{
int sum=;
while(n)sum+=n%,n/=;
return sum;
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int n;
while(cin>>n)//C++的输入，这样可以自己判断EOF，因为读到EOF的返回值为0
{
int num=;
for(int i=;;i++)
{
int sum=sum_of_digit(i),t=i;
for(int j=;j<i;j++)
{
if(t%j==)
{
while(t%j==)
{
sum-=sum_of_digit(j);
t/=j;
}
}
}
if(t==i||i==)continue;
if(sum==)num++;
if(num==n)
{
cout<<i<<"\n";//C++的输出函数，"\n"比endl要快
break;
}
}
}
}
直接交表的代码（确实不太能手算，我错了
#include<bits/stdc++.h>
using namespace std;
int num[]= {, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , };
int main()
{
int a;
while(~scanf("%d",&a))
{
printf("%d\n",num[a]);
}
return ;
}
5618: Kannyi爱干净
总提交: 272 测试通过:91
描述
Kannyi是一个非常爱干净的男孩子，他喜欢把自己东西都归回原位。
今天，Kannyi面对了一个问题，他要把他的袜子放进衣柜里。Kannyi的收纳包里有n双已经标过编号的袜子(每双袜子一对相同编号，从1到n)，现在袜子乱了，他想把它们成双放进衣柜里。他会随机从他的包里拿出来一只袜子，与此同时他寻找着桌上有没有一只袜子可以和拿出来的袜子配对。如果可以，他就会把它们一起放进衣柜里，否则他就把这只袜子放在桌子上。就这样，他把所有的袜子都整齐地放进了衣柜里。
现在Kannyi给你了他从收纳包取袜子的号码序列，请你告诉他桌子上出现过的最多袜子只数。
输入
输入数据包含多组测试实例，每个测试实例占两行。
第一行一个数n，表示Kannyi的袜子双数(1≤n≤10)。
第二行一共2n个整数，表示了Kannyi从收纳包依次取得的袜子号码a1，a2，...,a2n（1≤ai≤n）。
输出
每组样例输出收拾过程中桌子上出现过的最多袜子只数。
样例输入
1
1 1
3
2 1 1 3 2 3
样例输出
1
2
这个题目就是照抄Codeforces的A，但是原题要用hash方法，你们暂时没有学就标记变量就好啦
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
int a[]={},ma=;
for(int i=,x; i<*n; i++)
{
cin>>x;
a[x]++;
int f=;
for(int i=;i<=n;i++)
if(a[i]==)f++;
ma=max(ma,f);
}
cout<<ma<<"\n";
}
return ;
}
如果用set那就比较简单了，stl的学习可以到这篇博客
#include <bits/stdc++.h>
using namespace std;
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int n;
while(cin>>n)
{
n*=;
set<int>S;
int ma=;
for(int i=,x; i<n; i++)
{
scanf("%d",&x);
if(S.count(x))S.erase(x);
else S.insert(x);
ma=max((int)S.size(),ma);
}
cout<<ma<<"\n";
}
return ;
}
5620: Kannyi的正方体和圆柱体
总提交: 447 测试通过:175
描述
签到是不可能签到的，这辈子都不可能不签到的。
Kannyi现在有一个正方体和一个圆柱体，且两个是等高的，并且侧面积是相等。Kannyi很快知道了正方体的边长a，请聪明的你告诉他圆柱体的体积。
输入
输入数据包含多个测试实例，每个测试实例占一行，为一整数a(1 ≤ a ≤ 102)
输出
每行输出为圆柱体的体积V，保留1位小数。
样例输入
1
样例输出
1.3
提示
PI=acos(-1)
这个纯粹就是偷懒题，直接从高考卷拿了个选择题，不过高考卷是让求两者的比例的
相信同学们都能解出来正方体V：圆柱V=PI：4，好心提示了一波PI的较为精确值
#include<bits/stdc++.h>
using namespace std;
const double PI=acos(-);
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int n;
while(cin>>n)printf("%.1f\n",n*n*n*/PI);
}
当然你也可以这样，这个题目并不卡精度
#include<bits/stdc++.h>
#define PI acos(-1)
using namespace std;
int main()
{
int a;
while(cin>>a)
{
double sc=a*a*4.0;
double d=sc*1.0/a;
double r=d/2.0/PI;
double v=r*r*PI*a;
printf("%.1f\n",v);
}
return ;
}
5627: kannyi的独木桥
Total Submit: 24 Accepted:9
Description
kannyi的女神小M经常对kannyi说，你走你的独木桥（划重点），我走我的阳关道。kannyi不以为然，却对独木桥产生了浓厚的兴趣，并产生了一个问题：
独木桥的长度为m（1~m自西向东），每个人都有初始位置和初始方向，每个人每秒只能移动1个单位，当一个人到0或者m+1，则代表已经离开独木桥。每个人都会朝一个方向行走，中途不会自己改变方向。要是两人相遇，两人会分别转身继续行走 ，转身不需要时间。
现在kannyi想知道最早和最迟离开独木桥的人的时间。
Input
多组输入，第一行输入整数n，m，分别代表独木桥上的人数，桥的长度。（1<=n<=m<=1000000）
接下来n行，每行输入两个整数pi(1<=pi<=m)和di，分别代表第i个人的位置和朝向（di为-1时，朝向西，di为1时，朝向东），每个人的位置都不一样。
保证输入数据合法。
Output
输出一行，两个整数，分别为最早和最迟离开独木桥的人的时间（秒）。两个整数由一个空格符分开。
Sample Input
2 4
1 1
3 -1
Sample Output
3 4
Hint
样例解释：第一个人在1的位置，方向向东，第二个人在3的位置，方向向西，两人在位置2相遇，然后分别转向，第一个人离开独木桥所用时间就是1->2，2->1，1->0，用时3秒；第二个人离开独木桥所用时间就是3->2，2->3，3->4，4->5，用时4秒。
/*
我的口胡
但是题目保证数据合法了，问题就是相遇了怎么办，其实相遇了就是两者的时间的互换，自己可以试一下，因为每个人都要走到目标点的
所以朝向东就是自己走或者相遇者走m+1-a，朝向西就是自己走或者相遇者走a，分别取大取小就是答案
*/
#include<bits/stdc++.h>
using namespace std; int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int minn=1e9,maxx=;
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
minn=min(minn,b==?m-a+:a);
maxx=max(maxx,b==?m-a+:a);
}
printf("%d %d\n",minn,maxx);
}
return ;
}
5621: Kannyi的简单检查
Total Submit: 633 Accepted:149
Description
这里是2018年电信学院第一届新生程序设计竞赛 ，当然要和1有关了。大家都非常喜欢数字1，不管在游戏中还是现实中，都有个冠军梦。IG niubi！
Kannyi现在给你一个数字a，让你看看是否只含数字1，如果是请输出让人心动的"Accepted"，不是请输出令人心碎的"Wrong Answer"。
Input
输入数据包含多个测试实例，每个测试实例占一行，为整数a(-109≤ a ≤ 109)
Output
每个测试样例输出为1行，输出"Accepted"或"Wrong Answer"。
Sample Input
1
10
1111
2333
Sample Output
Accepted
Wrong Answer
Accepted
Wrong Answer
注意负数就好了，简单循环，当然你也可以进制转换
#include<bits/stdc++.h>
using namespace std;
int la(int x)
{
while(x)
{
if(abs(x%)!=)return ;
x/=;
}
return ;
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int x;
while(~scanf("%d",&x))
{
if(la(x))printf("Wrong Answer\n");
else printf("Accepted\n");
}
}
循环就完事的
#include<bits/stdc++.h>
using namespace std;
const double PI=acos(-);
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
char s[];
while(~scanf("%s",s))
{
int f=;
for(int i=; s[i]; i++)
{
if(s[i]=='-')continue;
else if(s[i]!='')f=;
}
if(f)printf("Wrong Answer\n");
else printf("Accepted\n");
}
}
5622: Kannyi的倒计时
Total Submit: 310 Accepted:160
Description
本次新生赛在12-08举办，工作人员需要执行出题、借教室等各种各样任务，但是这一群人有人有拖延症。
有句话怎么讲呢，deadline才是第一生产力，只要有某件事你看到需要迫切去做了，你就会去做。所以Kannyi要通过倒计时去刺激这些工作人员。
本次活动时间对于工作人员来说是11-12到12-10，所以请你算算给定工作时间距今天（12-08）有几天，为了区分在比赛前还是比赛后，请加上"+"、"-"号以便区别。
Input
输入数据包含多个测试实例，每个测试实例占一行，为一日期，格式为: "MM-DD"。
Output
每行输出为距离今天的天数x。
Sample Input
11-12
12-08
12-10
Sample Output
+26
0
-2
不要说没给a+b签到哦，算日期是典型的a+b（强行a+b
#include<bits/stdc++.h>
using namespace std;
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int m,d;
while(~scanf("%d-%d",&m,&d))
{
int ans;
if(m>)ans=-d;
else ans=-d;
if(ans>)printf("+");
printf("%d\n",ans);
}
}
5628: kannyi的开矿规划
Total Submit: 14 Accepted:1
Description
kannyi是某外星开矿公司的负责人，打算在某星球开矿。已知，这星球上的矿井都有对应的坐标点。一切开矿作业都靠开矿bot而非人类完成，飞船上只有一个传送门，请你思考一下在这颗星球上最多能获利多少。
*对传送门能做的所有操作：
1.启动：启动传送门需要消耗E1的电力，不消耗时间。
2.关闭：关闭传送门不消耗电力和时间。
3.修改：修改传送门的目标，不消耗电力和时间。但在传送门关闭的时候才能修改。修改的目标只能是每个矿井的入口处。
4.传送：当传送目标确定后并且传送门开启的时候，可以选择将任意数量的开矿bot传送到指定地点。这不消耗时间但是会消耗n*E2的电力(n为传送的bot的数量)，而将n个bot传送回来消耗的电力也相同。
5.维持：只要传送门启动着，每过一个单位时间就需要消耗E3的电力。
*对bot能做的操作：
1.移动：无论是上移或是下移，bot都会消耗1电力和1单位时间(电力充足无须担心)。从矿井入口下到地下单位一层也视作移动，从传送门到矿井入口不视作移动。
2.开采&装载：一个bot理论能承担至多25单位的矿物，开采25单位矿物消耗1电力和2单位时间(开采操作默认会直接挖够25矿物)，无论携带多少矿物都不影响bot的移动速度和消耗电力。
3.等待：等待不消耗电力。
*杂项：
1.1电消耗1钱，1矿换1钱，不存在电费梯度和矿物过度导致市场饱和问题。
2.中途赤字不影响开工。
3.传送门只有在指向某个坐标的时候，这个坐标的bot才能够传送回去。
4.消耗电力是每个bot单独计算，而时间层面，各个bot行动可以同时进行。
5.第n层没有挖掘不影响bot直接下到n层下面的移动动作。
Input
多组输入，每组的第一行是一个正整数N(1<=N<=100)，代表该星球上已经布置了多少坐标点，输入以N=0结束。
然后是三个正整数E1，E2和E3(1<=E2,E3<E1<=50)。
接下来是N对正整数ti和hi，ti表示该传送点下的矿井单位深度内有多少矿物，hi表示该矿井极限深度。(0<=ti<=500,ti%25=0,1<=hi<=10)。
Output
输出最多盈利额。
Sample Input
Sample Output
Hint
开门后传送5个bot过去，分别派遣到1-5层，挖掘结束后回到传送门回来。
bot共消耗35电量，花费总时间12单位，传送门则消耗15+1*12(等待)=27电量，实际获取矿物125单位。
所以最终盈利为53。
这个题目看懂题意，模拟一下就好了（看不懂或者感觉卡就对了，但是绝对是能做的
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,E1,E2,E3,t,h;
while(~scanf("%d",&n),n){
scanf("%d%d%d",&E1,&E2,&E3);
int ans=;
while(n--){
scanf("%d%d",&t,&h);
int maxx=,el=;
for(int i=;i<=h;i++){
el+=(*i+)*t/;
maxx=max(maxx,i*t-(min(*(i+)*E3,E1)+el+t*i/**E2+E1));
}
ans+=maxx;
}
printf("%d\n",ans);
}
return ;
}
5624: Kannyi的闯关游戏
Total Submit: 39 Accepted:15
Description
Kannyi最近迷上了一款通关的小游戏，是魔塔的简化版，现在继续将这个简化。
有一二维的图像，你可以在一个时间单位内进行上下左右移动，要通往下一关需要先去拿到钥匙，再去门口，是有时间限制的。现在Kannyi把图告诉你，希望你能告诉他最快可以在几个时间单位内到达，如果不能到达请输出"Oops! Something went wrong"（不包含引号）。
Input
题目包括多组测试数据。
每组测试数据以两个整数n,m(0<n, m≤20)开头，分别代表图像的长和高。紧接着有n行，m列字符，由"."，"#"，"S"，"K","E"组成。其中：
"." 代表能够行走的空地。
"#" 代表墙壁，人物不能从此通过，除此之外均可以通过。
"S" 是人物初始所在的位置。
"K" 是钥匙所在的位置。
"E" 是通往下一关的门的位置。
任务只能选择上、下、左、右任意一方向走一步。
Output
每组输出Kanny通过这一关的最短时间，如果不能达到输出"Oops! Something went wrong"。
Sample Input
1 3
SEK
4 4
....
....
..K.
S##E
4 4
....
...K
.###
S##E
Sample Output
3
5
Oops! Something went wrong
emmm，只有bfs可以找到最短路，dfs还是不要费力气了
我有了一个C++11的写法，打开C++11用这个
#include<bits/stdc++.h>
using namespace std;
struct T
{
int x,y,f;
}q[];
int d[][]={,,-,,,,,-};
char s[][];
bool vis[][];
int n,m,kx,ky;
int bfs(int x,int y)
{
memset(vis,,sizeof vis);
int tot=,sum=;
q[]={x,y,};//这个是c++11才支持的，其他版本你一个一个赋值就好
vis[x][y]=;
while(tot<sum)
{
for(int i=;i<;i++)
{
int nx=q[tot].x+d[i][],ny=q[tot].y+d[i][];
if(nx==kx&&ny==ky)return q[tot].f+;
if(nx>=&&ny>=&&nx<n&&ny<m&&vis[nx][ny]==&&s[nx][ny]!='#')
vis[nx][ny]=,q[sum++]={nx,ny,q[tot].f+};
}
++tot;
}
return ;
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
while(~scanf("%d%d",&n,&m))
{
for(int i=; i<n; i++)scanf("%s",s[i]);
int sx,sy,ex,ey;
for(int i=; i<n; i++)
for(int j=; j<m; j++)
{
if(s[i][j]=='K')kx=i,ky=j;
else if(s[i][j]=='S')sx=i,sy=j;
else if(s[i][j]=='E')ex=i,ey=j;
}
int ans=bfs(sx,sy)+bfs(ex,ey);
if(ans>)printf("Oops! Something went wrong\n");
else printf("%d\n",ans);
}
}
5625: Kannyi爱种树
Total Submit: 258 Accepted:6
Description
在一堂有趣的C语言实验课上，老师让同学们做一道题叫校门外的树，这时一个同学问我，这个题还有这么一个思路，（以下省略AC答案）。我一听，小伙子不错，这想法很奇妙，为了满足他的小需求（变态需求），我特地为他出了这么一个题。
Kannyi是一个植树队的队长，为了让城市变得更美好，他决定在城市的马路上种上树，于是他向*提出了申请，*很快就通过了，并给了一些要求。*要求Kannyi只允许在马路一侧种上树，并给他划出了一段总长为L米的马路。*还划定了M段连续的区域需要种上树。
Kannyi一看这么多要求头就大了，*划定的区域有长有短，有覆盖还有包含，这让他不知如何是好，愚蠢的他算了好几天也没算清楚到底要种几棵树，于是他找到了聪明的你，希望你能帮助他解决这个问题。
Input
第一行输入一个T代表一共T组数据，每组数据输入第一行包含两个非负整数L和M，L代表马路的总长度，M代表需要种树的区域。接下来M行，每行有两个数字a，b，代表区域[min(a,b)，max(a,b)]需要种上树。
数据保证：
T≈100
1<=L<=10^6
0<=M<=10^5
1<=a,b<=L
Output
输出包含一行，表示Kannyi的植树队满足*的所有需求后到底需要在马路上种多少颗树。
Sample Input
2
10 4
4 4
3 7
1 3
2 5
5 0
Sample Output
7
0
Hint
样例1：[1,7]被种上了树，一共种了7棵树。
样例2：没有地方被种上树。
这个题目数据范围非常之大，暴力标记什么的都是不行的，我们要使用线段求交，实质就是解决三种问题
————————
————————
————————
———————
————————
————
然后就可以愉快做题了
我的代码，等一波他们简单易懂的代码
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >V;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
V.clear();
int n;
scanf("%d%d",&n,&n);
for(int i=,x,y; i<n; i++)scanf("%d%d",&x,&y),V.push_back({min(x,y),max(x,y)});
sort(V.begin(),V.end());
int r=-,s=;
for(auto X:V)
{
if(X.second<=r)continue;
if(X.first>r) s+=X.second-X.first+;
else s+=X.second-r;
r=X.second;
}
printf("%d\n",s);
}
}
5626: Kannyi 的easy problem
Total Submit: 703 Accepted:103
Description
已知式子2n – 1，求该式子在1到n范围内能被7整除的正整数n的个数有多少个？
Input
多组输入，每组输入只有一个n(0<n<=1e18)，当n等于0时程序结束。
Output
输出范围内n的个数。
Sample Input
10
0
Sample Output
3
猜就完事，猜对了做不出来看看A的提示啊
这个题的证明可以这样来，2^n-1之后就是一个全为1的2进制数列
然后我进行求余，发现三位就是一循环（其实这就是编译原理的自动机
桃子的归纳法
#include<stdio.h>
int main()
{
__int64 n;
while(scanf("%I64d",&n),n)printf("%I64d\n",n/);
}
5629: Kannyi的复旦
Total Submit: 103 Accepted:11
Description
校园的天色逐渐暗了下来，教学楼里的人们也匆匆散去。Kannyi为了实现他小小的名校梦想，孑身一人坐在学习室里静修。不知不觉之中，时间过了零点。Kannyi的女神小M见状，便上前劝着Kannyi早些休息。然而Kannyi却依然沉迷在自己的考研真题中，丝毫没有困意。
于是，小M给Kannyi出了一道难题，如果Kannyi答错，就必须答应小M回去休息。但是Kannyi可不会轻易认输，便答应了小M的挑战：
小M给出了四个数列A,B,C,D，每个数列都包含着n个数。需要Kannyi从每个数列中各取出1个数，使4个数之和为0，并求出这样的组合个数。当一个数列中有多个相同数字时，把它们作为不同的数字看待。
Kannyi真的很想考上复旦大学^-^，所以他必须留下来继续学习，你能帮一帮为梦想执着的Kannyi嘛>o<！
Input
第一行输入n，表示各数列所含数字的个数。（1≤n≤4000）
接下来有4行，分别代表A,B,C,D数列，每行有n个数字。（|各数字的值|≤1000）
Output
符合条件的组合总数。
Sample Input
6
-45 -41 -36 -36 26 -32
22 -27 53 30 -38 -54
42 56 -37 -75 -10 -6
-16 30 77 -46 62 45
Sample Output
5
Hint
样例中符合条件的5种组合如下：
{-45 -27 42 30}
{26 30 -10 -46}
{-32 22 56 -46}
{-32 30 -75 77}
{-32 -54 56 30}
（二分或者用stl的hash unordered_map优化，打开C++11用这个
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=;
ll a[N],b[N];
unordered_map<ll,int> ma;
int main()
{
int n,i,j;
scanf("%d",&n);
for(i=;i<n;++i) scanf("%lld",&a[i]);
for(i=;i<n;++i) scanf("%lld",&b[i]);
for(i=;i<n;++i)
for(j=;j<n;++j)
++ma[a[i]+b[j]];
for(i=;i<n;++i) scanf("%lld",&a[i]);
for(i=;i<n;++i) scanf("%lld",&b[i]);
ll ans=;
for(i=;i<n;++i)
for(j=;j<n;++j)
ans+=ma[-a[i]-b[j]];
printf("%lld\n",ans);
return ;
}
出题人的代码
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAX 4005
int a[MAX],b[MAX],c[MAX],d[MAX];
int cd[MAX*MAX];
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
int n,i,j;
cin>>n;
for(i=;i<n;i++) scanf("%d",&a[i]);
for(i=;i<n;i++) scanf("%d",&b[i]);
for(i=;i<n;i++) scanf("%d",&c[i]);
for(i=;i<n;i++) scanf("%d",&d[i]);
for(i=;i<n;i++)
for(j=;j<n;j++)
cd[n*i+j]=c[i]+d[j];
sort(cd,cd+n*n);
long long res=;
for(i=;i<n;i++)
for(j=;j<n;j++)
{
int s=-a[i]-b[j];
res+=upper_bound(cd,cd+n*n,s)-lower_bound(cd,cd+n*n,s);
}
cout<<res<<endl;
return ;
}
对着库函数的二分实现一下，库函数的二分实现
#include<bits/stdc++.h>
using namespace std;
const int m=;
int n,a[m],b[m],c[m],d[m],cd[m*m];
int low(int key)
{
int step,mid,L=,R=n*n;
while(R>)
{
step=R>>,mid=L+step;
key>cd[mid]?(L=mid+,R=R-step-):(R=step);
}
return L;
} int up(int key)
{
int step,mid,L=,R=n*n;
while(R>)
{
step=R>>,mid=L+step;
key>=cd[mid]?(L=mid+,R=R-step-):(R=step);
}
return L;
}
int main()
{
int i,j;
long long sum=;
scanf("%d",&n);
for(i=; i<n; i++)
scanf("%d",&a[i]);
for(i=; i<n; i++)
scanf("%d",&b[i]);
for(i=; i<n; i++)
scanf("%d",&c[i]);
for(i=; i<n; i++)
scanf("%d",&d[i]);
for(i=; i<n; i++)
for(j=; j<n; j++)
cd[i*n+j]=c[i]+d[j];
sort(cd,cd+n*n);
for(i=; i<n; i++)
for(j=; j<n; j++)
{
int s=-a[i]-b[j];
sum+=up(s)-low(s);
}
cout<<sum;
return ;
}
没学会二分的这里看
#include<stdio.h>
#include<algorithm>
#define m 4005
int n,a[m],b[m],c[m],d[m],cd[m*m];
int low(int t)
{
int l=,r=n*n;
while(l<r)
{
int mi=l+(r-l)/;
if(cd[mi]<t)l=mi+;
else r=mi;
}
return l;
}
int up(int t)
{
int l=,r=n*n;
while(l<r)
{
int mi=l+(r-l)/;
if(cd[mi]<=t)l=mi+;
else r=mi;
}
return l;
}
int main()
{
int i,j;
long long sum=;
scanf("%d",&n);
for(i=; i<n; i++)
scanf("%d",&a[i]);
for(i=; i<n; i++)
scanf("%d",&b[i]);
for(i=; i<n; i++)
scanf("%d",&c[i]);
for(i=; i<n; i++)
scanf("%d",&d[i]);
for(i=; i<n; i++)
for(j=; j<n; j++)
cd[i*n+j]=c[i]+d[j];
std::sort(cd,cd+n*n);
for(i=; i<n; i++)
for(j=; j<n; j++)
{
int s=-a[i]-b[j];
sum+=up(s)-low(s);
}
printf("%I64d",sum);
return ;
}
简单的实现，有点慢
利用绝对值很小去hash，solution from zhouzexi
#include <bits/stdc++.h>
using namespace std;
unordered_map<int,int>mp[],mo;
int main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int n,x;
int T=;
cin>>n;
while(T--)
for(int i=;i<n;i++){
cin>>x;
mp[T][x]++;
}
unordered_map<int,int>::iterator it,it2;
for(it=mp[].begin();it!=mp[].end();it++)
for(it2=mp[].begin();it2!=mp[].end();it2++)
mo[it->first+it2->first]+=it->second*it2->second;
__int64 s=;
for(it=mp[].begin();it!=mp[].end();it++)
for(it2=mp[].begin();it2!=mp[].end();it2++)
s+=1LL*mo[-(it->first+it2->first)]*it->second*it2->second;
cout<<s<<endl;
}
数组的hash，可以0ms
#include <bits/stdc++.h>
using namespace std;
int ans[], M[][];
int main()
{
//freopen("test.in","r",stdin);
ios::sync_with_stdio(false), cin.tie(), cout.tie();
int n;
cin >> n;
int ma = , mi = ;
for (int j = ; j < ; j++)
for (int i = , x; i < n; i++)
{
cin >> x;
x = x + ;
ma = max(ma, x);
mi = min(mi, x);
M[j][x]++;
}
for (int i = mi; i <= ma; i++)
for (int j = mi; j <= ma; j++)
ans[i + j] += M[][i] * M[][j];
long long s = ;
for (int i = mi; i <= ma; i++)
for (int j = mi; j <= ma; j++)
s += 1LL * ans[ - (i + j)] * (M[][i] * M[][j]);
cout << s << endl;
}