Preface
又被输出格式创飞了，E题狂暴卡1h后面发现原来输出边的时候没有按照一小一大的顺序来输出
不过后面也没啥会的题了，几何、线代题做不来，对着一个四色定理题乱搞一波发现样例都过不去
值得一提的是这场前期完全是顺序开题，从A一直开到E
A. Digits Are Not Just Characters
签到
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=1005;
int n; vector <pi> v[N]; char s[N];
int main()
{
RI i,j; for (scanf("%d",&n),i=0;i<=n;++i)
{
scanf("%s",s+1); int m=strlen(s+1);
for (j=1;j<=m;)
{
if (('a'<=s[j]&&s[j]<='z')||('A'<=s[j]&&s[j]<='Z')) { v[i].push_back(pi(1,s[j])); ++j; continue; }
RI k=j; while (k<=m&&'0'<=s[k]&&s[k]<='9') ++k;
int x=0; for (;j<k;++j) x=x*10+s[j]-'0'; v[i].push_back(pi(0,x));
}
}
auto comp=[&](vector <pi>& A,vector <pi>& B)
{
for (RI i=0;i<min(A.size(),B.size());++i)
{
if (A[i]<B[i]) return true;
if (A[i]>B[i]) return false;
}
return A.size()<B.size();
};
for (i=1;i<=n;++i) puts(comp(v[i],v[0])?"-":"+");
return 0;
}
B. Arithmetic Progressions
徐神开场写的，我题目都没看
#include <bits/stdc++.h>
constexpr int $n = 5000;
int n, a[$n], dp[$n][$n], ans = 2;
int main() {
std::ios::sync_with_stdio(false);
std::cin >> n;
for(int i = 0; i < n; ++i) std::cin >> a[i];
std::sort(a, a + n);
for(int i = 0; i < n - 1; ++i) {
int p = i - 1;
for(int j = i + 1; j < n; ++j) {
dp[i][j] = 2;
while(p >= 0 && a[j] - a[i] > a[i] - a[p]) p--;
if(p >= 0 && a[j] - a[i] == a[i] - a[p]) dp[i][j] = dp[p][i] + 1;
if(dp[i][j] > ans) ans = dp[i][j];
}
}
std::cout << ans << char(10);
return 0;
}
C. Emergency Evacuation
纯是之前暑假做过的某个题的弱化版，而且结论是共通的
求出每个人走到出口的最短时间，排序后从小到大的取
如果之前这个时间出去的人已经存在，则当前的人只能选择往后延迟一个单位时间
用并查集维护一下向后第一个没被占用的时间点即可
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=500005;
int r,s,n,x,y,d[N],fa[N<<1];
inline int getfa(CI x)
{
return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
RI i; for (scanf("%d%d%d",&r,&s,&n),i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
if (y<=s) d[i]=s+1-y+r+1-x; else d[i]=y-s+r+1-x;
}
for (i=1;i<=n+r+s;++i) fa[i]=i;
for (sort(d+1,d+n+1),i=1;i<=n;++i)
{
int x=getfa(d[i]); if (i==n) printf("%d",x);
fa[x]=getfa(x+1);
}
return 0;
}
D. Shortest Common Non-Subsequence
徐神开场写的，建出序列自动机后大力DP一下即可
#include <bits/stdc++.h>
void gen(const char *s, int len, int nxt[][2]) {
int nn[2] = {len + 1, len + 1};
memcpy(nxt[len + 1], nn, sizeof(nn));
for(int i = len; i >= 0; --i) {
memcpy(nxt[i], nn, sizeof(nn));
if(i) nn[s[i] ^ 48] = i;
}
return ;
};
char s1[4004], s2[4004];
int l1, l2, nx1[4004][2], nx2[4004][2];
int dp[4004][4004];
char nch[4004][4004];
int main(void) {
scanf("%s%s", s1 + 1, s2 + 1);
l1 = strlen(s1 + 1), l2 = strlen(s2 + 1);
gen(s1, l1, nx1); gen(s2, l2, nx2);
// for(int i = 0; i <= l1 + 1; ++i) fprintf(stderr, "(%d,%d)%c", nx1[i][0], nx1[i][1], i == l1 + 1 ? 10 : 32);
// for(int i = 0; i <= l2 + 1; ++i) fprintf(stderr, "(%d,%d)%c", nx2[i][0], nx2[i][1], i == l2 + 1 ? 10 : 32);
// memset(dp, 0x7f, sizeof dp);
dp[l1 + 1][l2 + 1] = 0;
for(int i = l1 + 1; i >= 0; --i) for(int j = l2 + 1; j >= 0; --j) if(i < l1 + 1 || j < l2 + 1) {
int z1 = nx1[i][0], z2 = nx2[j][0];
int o1 = nx1[i][1], o2 = nx2[j][1];
if(dp[z1][z2] <= dp[o1][o2]) {
nch[i][j] = 0;
dp[i][j] = dp[z1][z2] + 1;
} else {
nch[i][j] = 1;
dp[i][j] = dp[o1][o2] + 1;
}
}
// fprintf(stderr, "dp00 = %d\n", dp[0][0]);
for(int i = 0, j = 0, nc = nch[i][j]; i < l1 + 1 || j < l2 + 1; i = nx1[i][nc], j = nx2[j][nc], nc = nch[i][j])
putchar(nc ^ 48);
putchar(10);
return 0;
}
E. Eulerian Flight Tour
挺有意思的一个细节分讨题
考虑一个图存在欧拉回路的充要条件有两个，一个是连通，另一个是每个点度数为偶数
不妨先考虑实现后者，我们可以把所有没有的边看作一个取值为\(0/1\)的变量，然后根据\(n\)个点的度数都要是偶数，可以列出\(n\)个异或方程
大力跑个bitset优化的高斯消元后，如果此时无解则最后必然无解，否则考虑怎么将得到的解转化成一个连通的解
不难发现当求出的解存在\(\ge 3\)个连通块时，我们只要在每个连通块内取一个点出来，然后连成一个环即可
那么此时剩下的就是有两个连通块的情况，首先若两个连通块内都有\(\ge 2\)个点，此时一定合法
具体就是设\(a,b\)来自一个连通块，\(c,d\)来自一个连通块，连边\(a\leftrightarrow c,a\leftrightarrow d,b\leftrightarrow c,b\leftrightarrow d\)即可
否则考虑一个连通块是孤点（记为\(a\)），另一个是非孤点的情况（两个都是孤点显然无解）
当非孤点的连通块不是一个完全图时，我们找到没有直接连边的两个点\(b,c\)，连边\(a\leftrightarrow b,a\leftrightarrow c,b\leftrightarrow c\)即可
同时还有一种情况，当非孤点的连通块中存在一条新加入的边时（记为\(b,c\)），可以删去\(b \leftrightarrow c\)的边，同时加入\(a\leftrightarrow b,a\leftrightarrow c\)的边
若以上均不满足，则原问题无解
#include<cstdio>
#include<iostream>
#include<bitset>
#include<vector>
#include<cstring>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=105,M=5005;
int n,m,x,y,deg[N],g[N][N],ng[N][N],u[M],v[M],tot,bel[N],idx,p[N],r[N];
vector <pi> ans; bitset <M> mat[N];
inline bool Gauss(CI n,CI m)
{
RI i,j; int bs=1; for (i=1;i<=n;++i)
{
int k=-1; for (j=bs;j<=m;++j) if (mat[j].test(i)) { k=j; break; }
if (k==-1) continue;
if (k!=bs) swap(mat[k],mat[bs]),swap(r[k],r[bs]);
for (j=1;j<=m;++j) if (bs!=j&&mat[j].test(i)) mat[j]^=mat[bs],r[j]^=r[bs];
p[bs++]=i; if (bs>m) break;
}
for (i=1;i<=m;++i) if (p[i]==-1&&r[i]) return 0;
return 1;
}
inline void DFS(CI now)
{
bel[now]=idx; for (RI to=1;to<=n;++to) if (g[now][to]&&!bel[to]) DFS(to);
}
inline void print(void)
{
printf("%d\n",ans.size());
for (auto [x,y]:ans) printf("%d %d\n",min(x,y),max(x,y));
}
int main()
{
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
scanf("%d%d",&x,&y),g[x][y]=g[y][x]=1,++deg[x],++deg[y];
for (i=1;i<=n;++i) for (j=i+1;j<=n;++j)
if (!g[i][j]) ++tot,u[tot]=i,v[tot]=j;
for (i=1;i<=n;++i)
{
for (j=1;j<=tot;++j) if (u[j]==i||v[j]==i) mat[i].set(j);
if (deg[i]&1) r[i]=1; p[i]=-1;
}
if (!Gauss(tot,n)) return puts("-1"),0;
for (i=1;i<=n;++i) if (r[i])
{
x=p[i]; g[u[x]][v[x]]=g[v[x]][u[x]]=ng[u[x]][v[x]]=ng[v[x]][u[x]]=1;
++deg[u[x]]; ++deg[v[x]]; ans.push_back(pi(u[x],v[x]));
}
for (i=1;i<=n;++i) if (!bel[i]) ++idx,DFS(i);
if (idx==1) return print(),0;
if (idx>=3)
{
vector <int> p; int vis[N]; memset(vis,0,sizeof(vis));
for (i=1;i<=n;++i) if (!vis[bel[i]]) p.push_back(i),vis[bel[i]]=1;
for (i=0;i<p.size();++i) ans.push_back(pi(p[i],p[(i+1)%p.size()]));
return print(),0;
}
vector <int> A,B; int a1=-1,a2=-1,b1=-1,b2=-1;
for (i=1;i<=n;++i) if (bel[i]==1) A.push_back(i); else B.push_back(i);
if (A.size()>=2&&B.size()>=2)
{
ans.push_back(pi(A[0],B[0])); ans.push_back(pi(A[0],B[1]));
ans.push_back(pi(A[1],B[0])); ans.push_back(pi(A[1],B[1]));
return print(),0;
}
for (i=0;i<A.size();++i) for (j=i+1;j<A.size();++j) if (!g[A[i]][A[j]]) a1=A[i],a2=A[j];
for (i=0;i<B.size();++i) for (j=i+1;j<B.size();++j) if (!g[B[i]][B[j]]) b1=B[i],b2=B[j];
if (a1!=-1)
{
ans.push_back(pi(a1,a2));
ans.push_back(pi(a2,B[0]));
ans.push_back(pi(B[0],a1));
return print(),0;
}
if (b1!=-1)
{
ans.push_back(pi(b1,b2));
ans.push_back(pi(b2,A[0]));
ans.push_back(pi(A[0],b1));
return print(),0;
}
for (i=0;i<A.size();++i) for (j=i+1;j<A.size();++j) if (ng[A[i]][A[j]]) a1=A[i],a2=A[j];
for (i=0;i<B.size();++i) for (j=i+1;j<B.size();++j) if (ng[B[i]][B[j]]) b1=B[i],b2=B[j];
if (a1!=-1)
{
for (RI i=0;i<ans.size();++i)
{
if ((ans[i].fi==a1&&ans[i].se==a2)||(ans[i].fi==a2&&ans[i].se==a1))
{
ans.erase(ans.begin()+i); break;
}
}
ans.push_back(pi(a1,B[0])); ans.push_back(pi(a2,B[0]));
return print(),0;
}
if (b1!=-1)
{
for (RI i=0;i<ans.size();++i)
{
if ((ans[i].fi==b1&&ans[i].se==b2)||(ans[i].fi==b2&&ans[i].se==b1))
{
ans.erase(ans.begin()+i); break;
}
}
ans.push_back(pi(b1,A[0])); ans.push_back(pi(b2,A[0]));
return print(),0;
}
return puts("-1"),0;
}
F. Fair Chocolate-Cutting
强劲几何题，从开场开到结束也不会做
G. What Goes Up Must Come Down
这题在我想E的时候祁神和徐神就搞出来了，我还是没太懂怎么做的
好像就是从小到大处理每种数，每次考虑把这种数往左移还是往右移，树状数组统计贡献，注意对相同的数的处理
#include <bits/stdc++.h>
using llsi = long long signed int;
int n;
int a[100001], c[100001], p[100000], s;
int main() {
std::ios::sync_with_stdio(false);
std::cin >> n;
for(int i = 1; i <= n; ++i) std::cin >> a[i], p[i - 1] = i;
std::sort(p, p + n, [](const int &x, const int &y) {
return a[x] < a[y];
});
for(int i = 1; i <= n; ++i) for(int j = i; j <= 100000; j += j&-j)
c[j] += 1;
int l = 0, r = 0;
s = n;
llsi ans = 0;
while(l < n) {
while(r < n && a[p[r]] == a[p[l]]) ++r;
// std::cerr << l << ", " << r << char(10);
for(int i = l; i < r; ++i) for(int j = p[i]; j <= 100000; j += j&-j)
c[j] -= 1;
s -= r - l;
for(int i = l; i < r; ++i) {
int l = 0, r;
for(int j = p[i]; j; j ^= j&-j) l += c[j];
r = s - l;
ans += std::min(l, r);
}
l = r;
}
std::cout << ans << char(10);
return 0;
}
H. Four-Coloring
很神奇的一个题
考虑按照横坐标从小到大，纵坐标从小到大的顺序给所有点排序，考虑增量法每次扩展一个点的颜色
由于新扩展的点一定在之前扩展的点集的右下方，因此其最多只有\(4\)个已经确定颜色的相邻节点
若新扩展的相邻节点中只有至多\(3\)种颜色，则直接赋一个剩下的颜色给它即可
否则不妨找到相邻的且颜色为\(1\)的点，找一条从它开始的，由颜色\(1,2\)交替组成的增广路
不难发现若存在这样的增广路，我们将上面的点的颜色全部取反后，最后新扩展的这个点的邻居中就没有颜色为\(1\)的点了
否则若不存在这样的增广路，那可以发现必然存在着一条由颜色\(3,4\)交替组成的增广路，同样地替换掉某种颜色即可
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=10005;
struct Point
{
int x,y,id;
friend inline bool operator < (const Point& A,const Point& B)
{
return A.x!=B.x?A.x<B.x:A.y<B.y;
}
}p[N]; int n,m,x,y,col[N]; vector <int> v[N];
inline int findcol(CI x)
{
static int vis[5]; memset(vis,0,sizeof(vis));
for (auto y:v[x]) vis[col[y]]=1;
for (RI i=1;i<=4;++i) if (!vis[i]) return i;
return 0;
}
inline void findpath(CI now,int x,int y)
{
col[now]=y; for (auto to:v[now]) if (col[to]==y) findpath(to,y,x);
}
int main()
{
RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
scanf("%d%d",&p[i].x,&p[i].y),p[i].id=i;
for (i=1;i<=m;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (sort(p+1,p+n+1),i=1;i<=n;++i)
{
int now=p[i].id; col[now]=findcol(now);
if (col[now]) continue;
for (auto to:v[now]) if (col[to])
{
for (RI c=1;c<=4;++c) if (c!=col[to])
{
findpath(to,col[to],c);
if (col[now]=findcol(now)) break;
}
if (col[now]) break;
}
}
for (i=1;i<=n;++i) printf("%d\n",col[i]);
return 0;
}
I. Ranks
线代FW表示完全不会做
J. Colorful Tree
经典重现，不过话说这比赛本身就是6年前的了
根据经典结论，树上若干个点组成的极小连通子树的边数，等于将所有点按照DFS序排序后，两两间距离和的二分之一（首尾也要算一次）
证明的话手玩一下就会发现按照上面那种方法最后每条极小连通子树中的边都会被经过两次
实现的话拿个set大力维护一下即可，复杂度由求树上距离的写法决定是否多带一个\(\log\)
#include <bits/stdc++.h>
constexpr int $n = 100000 + 10;
int n;
std::set<int> col[$n];
int cc[$n], dfn[$n], idfn[$n], dep[$n], vc[$n];
int dis(int a, int b);
void insert(int c, int vtx) {
col[c].insert(dfn[vtx]);
if(col[c].size() == 1) return ;
auto it = col[c].lower_bound(dfn[vtx]);
auto pre = it; if(pre == col[c].begin()) pre = col[c].end(); --pre;
cc[c] += dis(idfn[*pre], vtx);
auto nxt = it; ++nxt; if(nxt == col[c].end()) nxt = col[c].begin();
cc[c] += dis(idfn[*nxt], vtx);
cc[c] -= dis(idfn[*pre], idfn[*nxt]);
return ;
}
void remove(int c, int vtx) {
// assert(vc[vtx] == c);
auto it = col[c].lower_bound(dfn[vtx]);
if(col[c].size() == 1) return col[c].erase(it), void(0);
auto pre = it; if(pre == col[c].begin()) pre = col[c].end(); --pre;
// assert(vc[idfn[*pre]] == c);
cc[c] -= dis(idfn[*pre], vtx);
auto nxt = it; ++nxt; if(nxt == col[c].end()) nxt = col[c].begin();
// assert(vc[idfn[*nxt]] == c);
cc[c] -= dis(idfn[*nxt], vtx);
cc[c] += dis(idfn[*pre], idfn[*nxt]);
col[c].erase(it);
}
std::vector<int> out[$n];
int loop[$n][18];
void dfs(int now) {
static int O = 0;
dfn[now] = ++O; idfn[dfn[now]] = now;
dep[now] = dep[loop[now][0]] + 1;
for(int i = 1; i < 18; ++i) loop[now][i] = loop[loop[now][i - 1]][i - 1];
for(auto ch: out[now]) if(loop[now][0] != ch)
loop[ch][0] = now, dfs(ch);
}
int lca(int a, int b) {
if(dep[a] < dep[b]) std::swap(a, b);
for(int i = 17; ~i; --i) if(dep[loop[a][i]] >= dep[b])
a = loop[a][i];
if(a == b) return a;
for(int i = 17; ~i; --i) if(loop[a][i] != loop[b][i])
a = loop[a][i], b = loop[b][i];
return loop[a][0];
}
int dis(int a, int b) {
return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin >> n;
for(int i = 2, a, b; i <= n; ++i) {
std::cin >> a >> b;
out[a].push_back(b);
out[b].push_back(a);
}
dfs(1);
for(int i = 1; i <= n; ++i) {
std::cin >> vc[i];
insert(vc[i], i);
}
int q; std::cin >> q; while(q--) {
std::string s; std::cin >> s;
int v, c;
switch(s[0]) {
case 'Q':
std::cin >> c;
col[c].empty()
? std::cout << "-1\n"
: std::cout << cc[c] / 2 << char(10);
break;
case 'U':
std::cin >> v >> c;
remove(vc[v], v);
insert(vc[v] = c, v);
}
}
return 0;
}
K. Sixth Sense
首先如果没有字典序最大的话很容易求出最多赢几次，直接对于对方的每张牌，在我方剩余可用牌中找一个后继去对它即可，否则直接拿个最小的摆烂
考虑加上字典序的限制，套路地采用从前往后贪心确定的做法，但直接做复杂度是\(O(n^3)\)的（枚举位置，枚举放哪张牌，检验后面部分各\(O(n)\)）
考虑在哪里可以优化个复杂度，手玩下会发现在当前位置最优放哪张牌是满足二分性的
不过要注意的是需要分当前位置能赢对方和不能赢对方两种情况讨论，总复杂度\(O(n^2\log n)\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=5005;
int n,m,p[N],t[N],a[N],cur,mx; multiset <int> r,s;
inline bool check(CI pre,CI ban,int ret=0)
{
for (RI i=1,j=1;i<=m;++i)
{
while (j<=m&&(j==ban||a[j]<=p[i])) ++j;
if (j<=m) ++ret,++j;
}
return pre+ret==mx;
}
int main()
{
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&t[i]),p[i]=t[i];
for (i=1;i<=n;++i) scanf("%d",&a[i]);
for (sort(p+1,p+n+1),sort(a+1,a+n+1),i=j=1;i<=n;++i)
{
while (j<=n&&a[j]<=p[i]) ++j;
if (j<=n) ++mx,++j;
}
for (i=1;i<=n;++i) r.insert(p[i]),s.insert(a[i]);
for (i=1;i<=n;++i)
{
r.erase(r.find(t[i])); m=0; for (auto x:r) p[++m]=x;
m=0; for (auto x:s) a[++m]=x;
int pos=upper_bound(a+1,a+m+1,t[i])-a;
int l=pos,r=m,mid,ret=-1;
while (l<=r) if (check(cur+1,mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
if (ret==-1)
{
l=1; r=pos-1;
while (l<=r) if (check(cur,mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
} else ++cur;
s.erase(s.find(a[ret])); printf("%d ",a[ret]);
}
return 0;
}
Postscript
接下来两天大家都挺忙的，小小休息一波
标签：std,nxt,const,Contest,int,Regional,2018,include,col From： https://www.cnblogs.com/cjjsb/p/17997844