A. Automatic Door
对于规律的点可以推公式计算，对于噪点则暴力计算，时间复杂度$O(m\log m)$。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
const LL inf = 3e18;
void gmin(LL &x, LL y){if(y < x)x = y;}
LL t[N];
LL n, A, m, D;
int main()
{while(~scanf("%lld%lld%lld%lld", &n, &m, &A, &D)){for(int i = 1; i <= m; ++i)scanf("%lld", &t[i]);sort(t + 1, t + m + 1);m = unique(t + 1, t + m + 1) - t - 1;t[m + 1] = inf; //2e18LL p1 = 1, p2 = 1;LL num_in_D = D / A + 1;LL ans = 0;while(p1 <= n || p2 <= m){//get first timeLL now = inf;if(p1 <= n)gmin(now, p1 * A);if(p2 <= m)gmin(now, t[p2]);LL can = now + D;////printf("now = %lld\n", now);////if we start at a strange point, just try the 1 segmentif(p2 <= m && t[p2] == now){++ans;p1 = can / A + 1;p2 = upper_bound(t + p2, t + m + 1, can) - t; ////printf("p2 first: p1 = %d p2 = %d\n", p1, p2);//continue;}//find the first not covered p2, and all the before are in circlep2 = upper_bound(t + p2, t + m + 1, can) - t;////printf("p2=%d\n", p2);//LL ED = t[p2] - D - 1;LL lastp1 = min(ED / A, n);LL add = (lastp1 - p1 + 1 + num_in_D - 1) / num_in_D;////printf("ED = %lld lastp1 = %lld add = %lld\n", ED, lastp1, add);//ans += add;p1 += add * num_in_D;////getchar();//}printf("%lld\n", ans);}return 0;
}
/*
1 1 3 4
74 3 4 2
7 9 111000000000 0 1000000000 1000000000000000000999999999 0 1000000000 1000000000*/
B. Berland Army
首先若存在环则无解，否则通过DP可以求出每个数的最小值。
然后按照逆拓扑序，每次选择下界最小的点，填充最大的可以填充的值。
时间复杂度$O(m\log m)$。
#include<cstdio>
#include<algorithm>
#include<set>
#include<cstdlib>
#include<ctime>
#include<queue>
using namespace std;
typedef pair<int,int>P;
const int N=500010;
int n,m,K,i,a[N],f[N],x,y,g[N],v[N],nxt[N],ed,d[N];
int h,t,q[N];
int G[N],V[N],NXT[N],ED;
set<int>T;
int cnt[N];
struct E{int x,y;}e[N];
priority_queue<P>qu;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;d[y]++;
}
inline void ADD(int x,int y){V[++ED]=y;NXT[ED]=G[x];G[x]=ED;d[y]++;
}
bool can_vio(){long long t=1;for(int i=1;i<=n;i++)if(!a[i]){t*=K;if(t>1e9)return 0;}return 1;
}
inline bool check(){int i,j;for(i=1;i<=n;i++){for(int j=g[i];j;j=nxt[j])if(f[i]>=f[v[j]])return 0;}static bool used[N];for(i=1;i<=K;i++)used[i]=0;for(i=1;i<=n;i++)used[f[i]]=1;for(i=1;i<=K;i++)if(!used[i])return 0;return 1;
}
void dfs(int x){if(x>n){if(check()){for(int i=1;i<=n;i++)printf("%d ",f[i]);exit(0);}return;}if(a[x]){f[x]=a[x];dfs(x+1);return;}for(int i=1;i<=K;i++){f[x]=i;dfs(x+1);}
}
int main(){srand(time(NULL));scanf("%d%d%d",&n,&m,&K);for(i=1;i<=n;i++)scanf("%d",&a[i]),f[i]=max(1,a[i]);for(i=1;i<=m;i++)scanf("%d%d",&e[i].x,&e[i].y);random_shuffle(e+1,e+m+1);for(i=1;i<=m;i++){x=e[i].x,y=e[i].y;//x>yadd(y,x);//y<x}for(h=i=1;i<=n;i++)if(!d[i])q[++t]=i;while(h<=t){x=q[h++];for(i=g[x];i;i=nxt[i]){f[v[i]]=max(f[v[i]],f[x]+1);if(!(--d[v[i]]))q[++t]=v[i];}}if(t<n)return puts("-1"),0;for(i=1;i<=n;i++)if(a[i]&&f[i]!=a[i])return puts("-1"),0;for(i=1;i<=n;i++)if(f[i]>K)return puts("-1"),0;if(can_vio()){//dfs(1);}for(i=1;i<=K;i++)T.insert(i);for(i=1;i<=n;i++)if(a[i])T.erase(a[i]);for(i=1;i<=n;i++)T.erase(f[i]);for(i=1;i<=n;i++)cnt[f[i]]++;for(i=1;i<=n;i++)d[i]=0;for(i=1;i<=m;i++){x=e[i].x,y=e[i].y;//x>yADD(x,y);//y<x}for(i=1;i<=n;i++)if(!d[i])qu.push(P(f[i],i));while(!qu.empty()){P t=qu.top();qu.pop();x=t.second;for(i=G[x];i;i=NXT[i])if(!(--d[V[i]]))qu.push(P(f[V[i]],V[i]));if(a[x])continue;int lim=K;for(int j=g[x];j;j=nxt[j]){lim=min(lim,f[v[j]]-1);}//printf("%d %d %d\n",x,f[x],lim);set<int>::iterator it=T.lower_bound(lim);if(it!=T.begin()&&it==T.end())it--;while(it!=T.begin()&&(*it)>lim)it--;//if(it!=T.end())printf("it=%d\n",*it);bool flag=0;int old=f[x];if(it!=T.end()&&(*it)<=lim){if((*it)>f[x])f[x]=*it,flag=1;}if(flag){cnt[old]--;if(!cnt[old])T.insert(old);cnt[f[x]]++;T.erase(f[x]);}}if(T.size())return puts("-1"),0;for(i=1;i<=n;i++)if(a[i]&&f[i]!=a[i])return puts("-1"),0;for(i=1;i<=n;i++){for(int j=g[i];j;j=nxt[j])if(f[i]>=f[v[j]])return puts("-1"),0;}for(i=1;i<=n;i++)printf("%d ",f[i]);
}
C. Downloading B++
双指针枚举两种加油包的使用次数，时间复杂度$O(n)$。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
LL G, T, t0;
LL g1, t1, p1;
LL g2, t2, p2;
bool ok(LL G, LL T, LL num2)
{LL sum = min(G, num2 * g2);LL tim = sum * t2;return (G - sum) * t0 <= (T - tim);
}
int main()
{while (~scanf("%lld%lld%lld", &G, &T, &t0)){scanf("%lld%lld%lld", &g1, &t1, &p1);scanf("%lld%lld%lld", &g2, &t2, &p2);if (t1 > t2){swap(g1, g2);swap(t1, t2);swap(p1, p2);}if (t2 >= t0){t2 = t0;g2 = 1;p2 = 0;}LL top1 = (G + g1 - 1) / g1;LL top2 = (G + g2 - 1) / g2;LL ans = 9e18;for (int num1 = 0, num2 = top2; num1 <= top1; ++num1){LL sum = min(G, num1 * g1);LL tim = sum * t1;if (tim > T)break;//gmin(num2, (T - tim + t2 - 1) / t2);//while (num2 >= 0 && (G - sum) * t2 > (T - tim))--num2;while (num2 >= 0 && ok(G - sum, T - tim, num2)){gmin(ans, num1 * p1 + num2 * p2);--num2;}}if (ans == 9e18)ans = -1;printf("%lld\n", ans);}return 0;
}
D. Packmen Strike Back
若只有一个人，那么显然可以枚举他的方向。
否则一定可以拿到所有的物品，二分答案，DP求出前$i$个人能达到的最长前缀，最多只有连续两个人反向。
时间复杂度$O(n\log n)$。
E. Field of Wonders
按题意模拟即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
const int N=50 + 10,M=1010;
int n, m;
char s[N], a[M][N];
char ss[10];
bool e[M];
int main(){scanf("%d", &n);scanf("%s", s);scanf("%d", &m);for(int i = 1; i <= m; i ++){scanf("%s", a[i]);int o = 0;for(int j = 0; j < n; j ++){if(s[j] != '*'){if(a[i][j] != s[j]){e[i] = 1;}continue;}ss[0] = a[i][j]; ss[1] = 0;if(strstr(s, ss) == 0){a[i][o++] = a[i][j];}else{e[i] = 1;}}a[i][o] = 0;}int ans = 0;for(char ch = 'a'; ch <= 'z'; ch ++){ss[0] = ch; ss[1] = 0;if(strstr(s, ss) == 0){int flag = 1;for(int i = 1; i <= m; i ++){if(!e[i] && strstr(a[i], ss) == 0){flag = 0;break;}}if(flag) ans ++;}}printf("%d\n", ans);return 0;
}
F. Lost in Transliteration
将所有$u$换成$oo$，同时将所有$kh$换成$h$即可。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = 1e9;
int casenum, casei;
int n;
string s;
int main()
{while(~scanf("%d", &n)){set<string>sot;for(int i = 1; i <= n; ++i){cin >> s;while(1){ int pos = s.find("u");if(pos >= 0 && pos < s.size()){s.replace(pos, 1, "oo");}else break;}while(1){ int pos = s.find("kh");if(pos >= 0 && pos < s.size()){s.replace(pos, 2, "h");}else break;}sot.insert(s);}cout << sot.size() << endl;}return 0;
}
/**/
G. Orientation of Edges
从起点开始BFS，对于最多点数，则尽量把边往外定向；对于最少点数，则尽量把边往内定向。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
#define MS(x,y) memset(x, y, sizeof(x))
const int N = 3e5 + 10;
const int inf = 1e9;
int casenum, casei;
int n, m, g, top, S;
struct A
{int y, w, o;
};
int ans[N];
bool vis[N];
vector<A>a[N];
void BFS(int AIM)
{MS(ans, -1);MS(vis, 0);queue<int>q;q.push(S); vis[S] = 1;int ansnum = 0;while(!q.empty()){int x = q.front(); q.pop();++ansnum;for(auto it : a[x]){int y = it.y;int w = it.w;int o = it.o;if(vis[y])continue;if(w == 2 || AIM){q.push(y);vis[y] = 1;}if(ans[o] == -1){bool rev = AIM ^ w;ans[o] = rev;}}}printf("%d\n", ansnum);for(int i = 1; i <= g; ++i){printf("%c", ans[i] == 1 ? '-' : '+');}puts("");
}
int main()
{while(~scanf("%d%d%d", &n, &m, &S)){top = max(n, m);for(int i = 1; i <= top; ++i){a[i].clear();}g = 0;for(int i = 1; i <= m; ++i){int op, x, y;scanf("%d%d%d", &op, &x, &y);if(op == 2){++g;a[x].push_back({y, 1, g});a[y].push_back({x, 0, g});}else{a[x].push_back({y, 2, 0});}}BFS(1);BFS(0);}return 0;
}
/*
2 2 1
1 1 2
2 2 16 6 3
2 2 6
1 4 5
2 3 4
1 4 1
1 3 1
2 2 3
*/
H. Palindromic Cut
枚举段数，根据奇偶性分类讨论构造。
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=400010,M=200;
int n,i,j,c[M];
int cntodd;
char a[N],b[N],p[N];
inline int geteven(){for(int i=0;i<M;i++)if(c[i]&&c[i]%2==0)return i;return -1;
}
inline int getodd(int k=1){for(int i=0;i<M;i++)if(c[i]>=k&&c[i]%2==1)return i;return -1;
}
inline void check(int len){//each lengthif(n%len)return;int i,j;if(len%2==0){if(cntodd)return;for(i=0;i<M;i++)c[i]/=2;printf("%d\n",n/len);int k=0;for(i=0;i<n/len;i++){//each partfor(j=0;j<len/2;j++){while(!c[k])k++;p[j]=k;c[k]--;}for(j=0;j<len/2;j++)putchar(p[j]);for(j=len/2-1;~j;j--)putchar(p[j]);putchar(' ');}exit(0);}//len%2==1int ret=n/len-cntodd;if(ret<0)return;if(ret%2)return;printf("%d\n",n/len);for(i=0;i<n/len;i++){int k=getodd();if(k<0)k=geteven();c[k]--;for(j=0;j<len/2;j++){p[j]=geteven();if(p[j]<0)p[j]=getodd(3);c[p[j]]-=2;}for(j=0;j<len/2;j++)putchar(p[j]);putchar(k);for(j=len/2-1;~j;j--)putchar(p[j]);putchar(' ');}exit(0);
}
int main(){scanf("%d%s",&n,a);for(i=0;i<n;i++)c[a[i]]++;for(i=0;i<M;i++)if(c[i]%2)cntodd++;for(i=n;i;i--)check(i);
}
I. Photo Processing
二分答案，然后排序后DP，双指针+前缀和优化。
时间复杂度$O(n\log n)$。
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,i,l,r,mid,a[333333],ans,f[333333],s[333333];
bool check(){int i,j;f[0]=s[0]=1;for(i=1,j=0;i<=n;i++){while(a[i]-a[j+1]>mid)j++;int l=j,r=i-m;f[i]=0;if(l<=r)f[i]=!!(s[r]-s[l-1]);s[i]=s[i-1]+f[i];}return f[n];
}
int main(){scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);l=0,r=a[n]-a[1];while(l<=r){mid=(l+r)>>1;if(check())r=(ans=mid)-1;else l=mid+1;}printf("%d",ans);
}
J. Renovation
按价格从小到大考虑每个房子，在最靠后的能覆盖的地方拆掉这个房子，线段树维护可行性。
时间复杂度$O(n\log n)$。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
#define rt 1,1,top
#define ls o<<1
#define rs o<<1|1
#define mid (l+r>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int casenum, casei;
LL n, m;
LL a[N], suma[N];
int sta[N], top;
struct B
{LL b, p;bool operator < (const B & b)const{return p < b.p;}
}b[N];
LL flag[N * 4];
LL v[N * 4];
LL mn[N * 4];
void pushdown(int o)
{if(flag[o]){flag[ls] += flag[o];flag[rs] += flag[o];v[ls] -= flag[o];v[rs] -= flag[o];mn[ls] -= flag[o];mn[rs] -= flag[o];flag[o] = 0;}
}
void pushup(int o)
{mn[o] = min(mn[ls], mn[rs]);
}
void build(int o, int l, int r)
{flag[o] = 0;if(l == r){v[o] = suma[sta[l]];mn[o] = suma[sta[l]];return;}build(lson);build(rson);pushup(o);
}
int L, R, P; LL V;
LL check(int o, int l, int r)
{if(L <= l && r <= R){return mn[o];}pushdown(o);LL rtn = 1e18;if(L <= mid){rtn = min(rtn, check(lson));}if(R > mid){rtn = min(rtn, check(rson));}pushup(o);return rtn;
}
void dec(int o, int l, int r)
{if(L <= l && r <= R){flag[o] += V;v[o] -= V;mn[o] -= V;return;}pushdown(o);if(L <= mid)dec(lson);if(R > mid)dec(rson);pushup(o);
}
int main()
{while(~scanf("%lld%lld", &n, &m)){for(int i = 1; i <= n; ++i){scanf("%lld", &a[i]);suma[i] = suma[i - 1] + a[i];}for(int i = 1; i <= m; ++i){scanf("%lld", &b[i].b);}for(int i = 1; i <= m; ++i){scanf("%lld", &b[i].p);}sort(b + 1, b + m + 1);top = 0;for(int i = 1; i <= n; ++i){while(top && a[i] >= a[sta[top]])--top;sta[++top] = i;}build(rt);int ans = 0;for(int i = 1; i <= m; ++i){int l = 0;int r = top;while(l < r){int md = (l + r + 1) / 2;if(a[sta[md]] >= b[i].b){l = md;}else r = md - 1;}if(l){L = l;R = top;LL val = check(rt);if(val >= b[i].p){++ans;V = b[i].p;dec(rt);}}}printf("%d\n", ans);}return 0;
}
/**/
K. Road Widening
首先将每个数都拨高到最大限度，然后正反两边递推满足差值的限制即可。
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1000010;
int n,i,f[N],s[N],g[N];long long ans;
int main(){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&s[i],&g[i]),f[i]=s[i]+g[i];for(i=2;i<=n;i++)f[i]=min(f[i-1]+1,f[i]);for(i=n-1;i;i--)f[i]=min(f[i+1]+1,f[i]);for(i=1;i<=n;i++)if(f[i]<s[i])return puts("-1"),0;for(i=1;i<=n;i++)ans+=f[i]-s[i];printf("%I64d\n",ans);for(i=1;i<=n;i++)printf("%d ",f[i]);
}
L. Berland.Taxi
按题意模拟。
M. Quadcopter Competition
答案为两倍的曼哈顿距离加上一点微调距离。
#include<cstdio>
int a,b,c,d,x,y,ans;
int abs(int x){return x>0?x:-x;}
int main(){scanf("%d%d%d%d",&a,&b,&c,&d);x=abs(a-c);y=abs(b-d);if(x*y==0)ans=x+y+3;else ans=x+y+2;printf("%d",ans*2);
}
