好，好难
https://ac.nowcoder.com/acm/contest/5477
A.
题目描述
天才程序员菜哭武和张老师有一天到一个城市旅游，旅途中菜哭武觉得无聊就想和张老师玩一个游戏。菜哭武有n个石子，每个石子都标有1到n之间到数，且各不相同，一开始他们会随机从这堆石子选一个石子放置到一个集合中，张老师选的数是a，菜哭武选的是b（a和b不相同）。接下来菜哭武和张老师轮流按照如下规则拿走一个石子：当石子x能被拿走时，当且仅当集合存在y和z，满足x等于y+z或者y-z，当x被拿走时，把它放到集合中。谁完成最后一轮操作时，谁获胜。张老师总是先手，于是张老师就好奇当决定好a和b时，他是否总是能获胜，你能帮助一下张老师吗？
输入描述:
第一行一个整数T（1≤T≤500），表示共有T组测试数据。
对于每组测试数据，第一行三个整数n（2≤n≤20000）、a和b（1≤a,b≤n, a≠b）。
输出描述:
若张老师能获胜输出Yes，反之No。
示例1
输入
16
2 1 2
3 1 3
67 1 2
100 1 2
8 6 8
9 6 8
10 6 8
11 6 8
12 6 8
13 6 8
14 6 8
15 6 8
16 6 8
1314 6 8
1994 1 13
1994 7 12
输出
No
Yes
Yes
No
No
No
Yes
Yes
No
No
Yes
Yes
No
Yes
No
No
数学题。可以看到能拿到的石子一定是y和z的线性组合。在1到n里能表示为yz线性组合的数一共有n/gcd(y,z)个（向下取整），判断其奇偶性即可。
#include <bits/stdc++.h> using namespace std; int gcd(int a,int b) { return b?gcd(b,a%b):a; } int main() { int t; cin>>t; while(t--) { int n,a,b; cin>>n>>a>>b; int ans=n/gcd(a,b); if(ans&1) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
B.
题目描述
勇士菜哭武获得了一把新的武器，武器有特殊的伤害计算方式。武器的伤害计算方式由若干个部分的和组成,用+号连接。每一部分可以是一个整数a，或者是一个公式ndx。其中a表示固定伤害a点；ndx表示掷n个x面骰子，伤害是所有骰子点数的和。总伤害是每一部分伤害的和。
比如2d6+1d70+3，表示掷两个6面骰子和一个70面骰子（不一定实际存在70面骰子，可以理解成1到70当中随机选择一个整数），再加上固定伤害3点。
他正准备挑选一把好武器，需要计算新武器的伤害期望值，想让你帮他计算一下。
输入描述:
输入一个字符串，表示伤害计算公式。字符串长度不超过5000，对于每一个部分，1≤a, n, x≤1000。a,n,x都是整数。
输出描述:
输出一个数，表示伤害的期望值。如果不是整数，小数点后位数保留最少，即最终结果只有可能是整数或者小数点后是.5的形式，如果不是整数，那么保留一位小数。
示例1
输入
1d6+1d70+1d10+6
输出
50.5
人生苦短自己太菜了所以用的Python(用的还很烂)
isinstance(ans,int)判断整数还是很香的。
垃圾代码仅供参考
s=input() ans=0 lst=s.split('+') for ss in lst: if ss.find('d') != -1: lst1=ss.split('d') ans+=int(lst1[0])*( 1/int(lst1[1])* ( (1+int(lst1[1]))*int(lst1[1])/2) ) else: ans+=int(ss) if isinstance(ans,int): print(ans) else: temp=str(ans) pos=temp.find('.') if int(temp[pos+1])<=4: print(int(ans)) else: print(str(int(eval(temp)))+".5")
D.
题目描述
张老师设计了一个智能调度系统来控制他的遥控车队，今天，他带着他的车队来到黄渡理工大学的一块空地上测试这个系统。
这块空地可以描述为一个 w * h 大小的长方形，广场上有一些障碍物，几个目标点，当然，还有张老师的车队。
每分钟，调度系统会智能地向其中的一辆遥控车发送以下指令的其中一条：
- 向北走，直到撞到空地的边界、障碍物或其他遥控车；
- 向南走，直到撞到空地的边界、障碍物或其他遥控车；
- 向西走，直到撞到空地的边界、障碍物或其他遥控车；
- 向东走，直到撞到空地的边界、障碍物或其他遥控车；
每条指令都会在一分钟之内完成，也就是说，空地上最多只有一辆遥控车在运动。此外，当遥控车无法向相应的方向移动时，它会停在原地。
你想知道，在第 k 分钟时，有没有可能有任意一辆遥控车处在任意一个目标点上。
输入描述:
第一行输入三个数字w, h, k (1 ≤ w, h ≤ 10, 1 ≤ k ≤ 5) ,含义在题目描述中已给出。
接下来h行，每行输入一个长度为w的字符串si，其中第i行的第j个字符表示(i, j)位置的状态。
其中，'R'代表该位置初始有一辆遥控车，'X'代表该位置有障碍物，'D'代表该位置是一个目标点，'.'代表该位置可以正常通过。
数据保证广场上的遥控车不超过4辆。
输出描述:
如果k分钟后有可能有任意一个遥控车处在任意一个目标点上，输出YES,否则输出NO。
示例1
输入
6 5 4
.....R
...X..
..D...
....D.
R.R...
输出
YES
一开始没注意数据范围简直神级难题，结果一看其实是暴搜。注意因为车是动态的，其实可以直接把车用结构体存储+另开一个vis数组标记当前位置，地图上车的位置直接换成,即可。
#include <bits/stdc++.h> using namespace std; char mmap[13][13]; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int vis[13][13]={0}; struct car { int x; int y; }c[105]; int w,h,k,cnt=0; bool flag=0; bool check() { int i; for(i=1;i<=cnt;i++) { if(mmap[c[i].x][c[i].y]=='D') return 1; } return 0; } void dfs(int ttime)//在time时刻 { int i,j; if(ttime==k+1) { if(check()) flag=1; return; } for(i=1;i<=cnt;i++)//选车 { for(j=0;j<4;j++) { car ori=c[i]; vis[c[i].x][c[i].y]=0; while(c[i].x<=h&&c[i].y<=w&&c[i].x>=1&&c[i].y>=1&&mmap[c[i].x][c[i].y]!='X'&&(!vis[c[i].x][c[i].y])) { c[i].x+=dir[j][0]; c[i].y+=dir[j][1]; } c[i].x-=dir[j][0]; c[i].y-=dir[j][1]; vis[c[i].x][c[i].y]=1; vis[ori.x][ori.y]=0; dfs(ttime+1); vis[c[i].x][c[i].y]=0; vis[ori.x][ori.y]=1; c[i]=ori; } } } int main() { cin>>w>>h>>k; int i,j; for(i=1;i<=h;i++) { scanf("%s",mmap[i]+1); } for(i=1;i<=h;i++) { for(j=1;j<=w;j++) { if(mmap[i][j]=='R') { mmap[i][j]='.'; c[++cnt]={i,j}; vis[i][j]=1; } } } dfs(1); if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; }
F.
题目描述
天才程序员菜哭武和石头组队参加一个叫做国际排列计算竞赛 (International Competition of Permutation Calculation, ICPC) 的比赛，这个比赛的规则是这样的：
一个选手给出一个长度为 n 的排列，另一个选手给出 m 个询问，每次询问是一个形如 (l, r) 的数对，查询队友给出的排列中第 l 个数到第 r 个数的和，并将查询到的这个区间和加入总分，最后总分最高的队伍就能获胜。
石头手速很快，在比赛一开始就给出了 m 个询问；菜哭武也很强，他总是能找到最合适的排列，使得他们队的总分尽可能高。
在看比赛直播的你看到了石头给出的 m 个询问，聪明的你能不能预测出他们队伍最终的得分呢？
一个排列是一个长度为 n 的数列，其中 1 ~ n 中的每个数都在数列中恰好出现一次。比如 [1, 3, 2] 是一个排列，而 [2, 1, 4] 和 [1, 2, 3, 3] 不是排列。
输入描述:
第一行输入两个数 n (1≤n≤2×105) 和 m (1≤m≤2×105) 。
接下来 m 行，每行输入两个数 l 和 r ，代表这次查询排列中第 l 个到第
r 个的和。
输出描述:
输出一个整数，代表他们队伍总分的最大值。
示例1
输入
7 3
1 3
3 7
5 6
输出
46
说明
一个符合条件的排列是 [1,3, 6, 4, 7, 5, 2]，于是最终的得分为 (1 + 3 + 6) + (6 + 4 + 7 + 5 + 2) + (7 + 5) = 46
查询一次区间相当于给这个区间的查询次数+1，可以用差分实现。最后贪心地给查询次数较多的位置分配较大的数，计算答案即可（记得long long+快读
#include <bits/stdc++.h> using namespace std; int n,m,diff[200005]={0}; inline int read()//不加快读会T { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } int main() { cin>>n>>m; int i; for(i=1;i<=m;i++) { int l,r; l=read(),r=read(); diff[l]++;diff[r+1]--; } for(i=1;i<=n;i++) diff[i]+=diff[i-1]; sort(diff+1,diff+n+1); long long ans=0; for(i=n;i>=1;i--) { ans+=(long long)i*diff[i]; } cout<<ans; return 0; }