目录
2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest
比赛情况
| 题号 | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 状态 | O | - | O | O | - | O | O | O | O | - |
O 在比赛中通过 Ø 赛后通过 ! 尝试了但是失败了 - 没有尝试
比赛时间
2020-06-14 13:00-18:00
提交记录
A: Wrong Answer 2020-06-14 13:47 *3
A: Accepted 2020-06-14 13:49
D: Accepted 2020-06-14 14:00
H: Wrong Answer 2020-06-14 15:19 *3
H: Accepted 2020-06-14 15:28
C: Accepted 2020-06-14 15:42
G: Accepted 2020-06-14 16:16
F: Wrong Answer 2020-06-14 17:46 *7
F: Accepted 2020-06-14 17:58
题解
A.Advertising Strategy
目标订购者为$n$，总花费$k$。$a_i$为当前订购者数量，每天可以花费$x_i$使得$b_i=a_i+x_i$，之后$a_{i+1}=b_i+\min(b_i,\lfloor\frac{n-b_i}2\rfloor)$，问达到目标订购的最少天数
题解：显然至少要有花费要在最后一天给出，其他钱应该是早花早受益，于是在第一天和最后一天花钱。枚举在第一天花的钱，模拟天数增加直到剩下的人可以一次性花钱补全。
code:
C.Carpet
要将$n(1\le n\le 100000)$个点的树铺在$1000000×20$的坐标平面里，使得边与边无端点之外的重合点。
题解：树剖，将轻儿子往上放，重儿子往右放。
code:
D. Decoding of Varints
题意
语文题，就是给了一个类似128进制的定义，然后给一个未知的序列，对于这个序列中的每一个数字，如果这个数字$\geq 0$的时候，这个数就变为这个数字的二倍，奇遇的时候是这个数字相反数的二倍再减一，把新数字搞成他之前定义的形式中的每一位，现在给你每一位，让你装换回去。
数据范围
$n\leq 10000$
题解
就 模拟啊
代码
F. Fake or Leak
反正就是大模拟。。码力和英语都好差，写了好多次才过
<hidden> #include<bits/stdc++.h> #define ll long long #define pii_ pair<int,int> #define mp_ make_pair #define pb push_back #define fi first #define se second #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define show1(a) cout<<#a<<" = "<<a<<endl #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl using namespace std; const ll INF = 1LL<<60; const int inf = 1<<30; const int maxn = 1005; inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} int n,m,k,a,t; int nowTime[maxn],nowSolve[maxn],has[maxn],bestTime[maxn],in[maxn],finalAc[maxn]; char op; string name,laterName[maxn],rn[maxn]; map<string,int> mp; void GG() { cout<<"Fake"<<endl; exit(0); } struct node { string name; int solve,time,fac; bool operator <(node e){ if(solve!=e.solve) return solve>e.solve; if(time!=e.time) return time<e.time; if(fac!=e.fac) return fac<e.fac; return name<e.name; } }; vector<node> team; vector<string> res; int main() { fastio(); cin>>n>>m>>k; rep(j,1,m){ cin>>name; mp[name] = j; rn[j] = name; rep(i,1,n){ cin>>op>>a>>t; if(op=='+'){ nowTime[j] += 20*(a-1)+t; nowSolve[j]++; bestTime[j] += 20*(a-1)+t; finalAc[j] = max(finalAc[j],t); } else bestTime[j] += 20*a+240; } } rep(j,1,k){ cin>>laterName[j]; name = laterName[j]; int ti = 0,so = 0,fac=0; has[mp[name]] = 1; rep(i,1,n){ cin>>op>>a>>t; if(op=='+'){ ti += 20*(a-1)+t; so++; fac = max(fac,t); } } team.pb((node){name,so,ti,fac}); } rep(i,1,m){ if(!has[i]){ team.pb((node){rn[i],nowSolve[i],nowTime[i],finalAc[i]}); if(nowSolve[i]<n) team.pb((node){rn[i],n,bestTime[i],240}); else team.pb((node){rn[i],n,bestTime[i],finalAc[i]}); } } sort(team.begin(),team.end()); int cnt = 0,flag = 0; for(node x:team){ if(has[mp[x.name]]) flag = 1; if(flag && cnt<k){ if(has[mp[x.name]]) {res.pb(x.name);cnt++;} else { in[mp[x.name]]++; if(in[mp[x.name]]==2) GG(); } } } rep(i,1,k){ if(res[i-1]!=laterName[i]) GG(); } cout<<"Leaked"<<endl; return 0; }
</hidden>
G. God of Winds
一个网格图，每个小正方形的边有个权值。可以任选格子，加入一个顺时针或者逆时针的风，用来改变格子周围四条边的权值。右和下是正方形，题目给定权值，问这样的图是否存在。 注意到每条边只有两个格子能影响它，假设每个 $(i,j)$ 处的格子有 $x_{i,j}$ 个顺时针方向的风，那么整个图就是个等式的差分约束，对每个变量连边然后 $\text{dfs}$ 一遍，判断会不会有矛盾的点。
<hidden> #include<bits/stdc++.h> #define ll long long #define pii_ pair<int,int> #define mp_ make_pair #define pb push_back #define fi first #define se second #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define show1(a) cout<<#a<<" = "<<a<<endl #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl using namespace std; const ll INF = 1LL<<60; const int inf = 1<<30; inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} const int maxn = 250005; int n,m; int r[505][505],c[505][505]; int vis[maxn],head[maxn],tot; ll dis[maxn]; struct edge { int u,v,w,nxt; }es[maxn<<2]; void add(int u,int v,int w) { es[++tot] = (edge){u,v,w,head[u]}; head[u] = tot; } void dfs(int u) { vis[u] = 1; for(int i=head[u];~i;i=es[i].nxt){ int v = es[i].v,w = es[i].w; if(!vis[v]){ dis[v] = dis[u] + w; dfs(v); }else{ if(dis[v]!=dis[u]+w){ cout<<"No"<<endl; exit(0); } } } } int main() { fastio(); memset(head,-1,sizeof(head)); cin>>n>>m; rep(i,0,n-1)rep(j,0,m-1){ cin>>r[i][j]>>c[i][j]; } rep(i,0,n-1){ rep(j,0,m-1){ int u = i*m+j,v = (i-1+n)%n*m + j; add(u,v,r[i][j]);add(v,u,-r[i][j]); int x = i*m+j,y = i*m + (j-1+m)%m; add(x,y,-c[i][j]);add(y,x,c[i][j]); } } dfs(0); cout<<"Yes"<<endl; return 0; }
</hidden>
H. Hilarious Cooking
题意
希望你构造一个序列，序列相邻两个数差值不超过1，和为T，然后其中有一些给定位置的给定数字，问能否构造成功。
数据范围
序列的长度$n\leq 2\times 10^9$，$1\leq T\leq 10^{18}$
给定的数字个数$1\leq m\leq 100000$
题解
可以考虑，构造这样一个序列可以保证在一个范围内连续，因为除非在最大值和最小值的位置，其他情况下都可以找到一个位置+1或者找到一个位置-1并符合序列规定，那么我们要做的就是确定这个序列可能的最大值和可能的最小值。注意到其限制其实就是给定的数字，最大值在两个给定的数字构造一个像山顶或山坡的形状，最小值就构造一个山谷或山坡一样的形状即可，要注意一些细节，比如最开始和最后的。
代码
