Preface
合肥前的最后一场VP了，本来计划是我和祁神两个人打，但后面徐神还是来救场了
然后这场我们过的最难的两题都是徐神切的，直接给我们抬进Au区了属于是
而且徐神最后也差一点写出G（TLE on 72），同时也一眼秒了D（没时间写了），看来这场让三个徐神来打感觉10题随便出线了
A. A Bite of Teyvat
防AK几何题，做不了一点
B. Bitwise Exclusive-OR Sequence
很典的题，感觉已经见过114514种类似的idea了
异或操作考虑按位操作，单独讨论二进制下每一位，把位置看作图，限制看作边权为\(0/1\)的边
不难发现一个连通块内的点都会相互制约，合法性可以用黑白染色判断一下
然后要求选的数的和最少，只需要统计下每个连通块内两种颜色的点的个数，取个数较少的染成\(1\)即可
具体实现的时候可以把所有位一起处理，可以大大减小常数，总复杂度\(O(m\log a_ii)\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int, int>;
#define ft first
#define sd second
const int B = 32;
const int N = 2e5+5;
int n, m;
int fa[N], sz[N];
struct Edge{int u, v, w;};
vector<pii> G[N];
vector<Edge> edg;
int cnt[N][B];
int col[N];
bool vis[N];
int gf(int x){return x==fa[x] ? x : fa[x]=gf(fa[x]);}
void dfs(int x){
for (auto [to, w] : G[x]){
if (col[to]!=-1) continue;
col[to]=w^col[x];
dfs(to);
}
}
void dfs2(int x, int id){
for (int b=0; b<=30; ++b) if (col[x]&(1LL<<b)) ++cnt[id][b];
vis[x]=true;
for (auto [to, w] : G[x]){
if (!vis[to]) dfs2(to, id);
}
}
signed main(){
scanf("%lld%lld", &n, &m);
for (int i=1; i<=n; ++i) fa[i]=i, sz[i]=1;
for (int i=1; i<=m; ++i){
int a, b, w; scanf("%lld%lld%lld", &a, &b, &w);
G[a].push_back(make_pair(b, w)); G[b].push_back(make_pair(a, w));
edg.push_back(Edge{a, b, w});
int x=gf(a), y=gf(b);
if (x!=y) sz[x]+=sz[y], sz[y]=0, fa[y]=x;
}
memset(col, -1, (n+1)*sizeof(int));
for (int i=1; i<=n; ++i) if (i==gf(i)){
col[i]=0; dfs(i); dfs2(i, i);
}
bool ok=true;
for (auto [u, v, w] : edg){
if ((col[u]^col[v])!=w){ok=false; break;}
}
// for (int i=1; i<=n; ++i){
// printf("i=%lld sz=%lld\n", i, sz[i]);
// for (int b=0; b<=30; ++b) printf("%lld ", cnt[i][b]); puts("");
// }
if (!ok) printf("-1\n");
else{
int ans=0;
for (int i=1; i<=n; ++i) if (gf(i)==i){
for (int b=0; b<=30; ++b){
int tmp=min(sz[i]-cnt[i][b], cnt[i][b]);
ans += (1LL<<b)*tmp;
}
}
printf("%lld\n", ans);
}
return 0;
}
C. Cards of Magic
好复杂的题意，一眼G
D. Cross the Maze
徐神比赛的时候一眼秒了，但还剩下1h被我骗去写G了，到时候看看能不能蛊惑徐神赛后把这题补了
E. Edward Gaming, the Champion
签到
#include<cstdio>
#include<iostream>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
char s[N];
int main()
{
//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
scanf("%s",s+1); int n=strlen(s+1),ans=0;
for (RI i=1;i+4<=n;++i)
if (s[i]=='e'&&s[i+1]=='d'&&s[i+2]=='g'&&s[i+3]=='n'&&s[i+4]=='b') ++ans;
return printf("%d",ans),0;
}
F. Encoded Strings I
签到，模拟一遍即可
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int n,chs[30]; char s[N]; string ans;
int main()
{
//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
RI i,j; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
{
for (j=0;j<20;++j) chs[j]=-1;
int cur=0; string tmp="";
for (j=i;j>=1;--j)
{
if (!~chs[s[j]-'a']) chs[s[j]-'a']=cur,++cur;
tmp+=char(chs[s[j]-'a']+'a');
}
reverse(tmp.begin(),tmp.end());
if (tmp>ans) ans=tmp;
}
return cout<<ans,0;
}
G. Encoded Strings II
祁神刚开始Rush了贪心，然后被徐神叉掉了，随后徐神又秒出了个DP的做法
可惜\(O(n\times 2^{20})\)没能跑出来，后面感觉可以优化成\(O(20^2\times 2^{20})\)，据说这样就能过了
这里就放一个\(O(n\times 2^{20})\)的代码吧
#include <bits/stdc++.h>
std::string dfs(std::string s) {
if(s.size() == 0) return "";
std::bitset<20> bs;
int n = s.size(), i, ue, cc;
for(char c: s) bs[c - 'a'] = 1;
cc = bs.count();
bs.reset();
for(i = n - 1; i >= 0 && bs.count() < cc; --i) bs[s[i] - 'a'] = 1;
ue = i + 1;
std::vector<int> occur(20, 0);
for(i = 0; i <= ue; ++i) occur[s[i] - 'a'] += 1;
int mo = occur[0]; std::vector<int> maxOccur = {0};
for(i = 1; i < 20; ++i) {
if(occur[i] > mo) mo = occur[i], maxOccur.clear(), maxOccur.push_back(i);
else if(occur[i] == mo) maxOccur.push_back(i);
}
// for(int i = 0; i < 20; ++i) std::cerr << occur[i] << char(i == 19 ? 10 : 32);
std::string pre = "", res = "";
for(i = 0; i < mo; ++i) pre += char('a' + cc - 1);
// std::cerr << "pre = " << pre << char(10);
for(int rem: maxOccur) {
std::string ss = "";
int lasOccur = -1;
for(i = 0; i <= ue; ++i) if(s[i] == rem + 'a') lasOccur = i;
for(i = lasOccur + 1; i < n; ++i) if(s[i] != rem + 'a') ss += s[i];
std::string subRes = dfs(ss);
if(subRes > res) std::swap(res, subRes);
}
return pre + res;
}
int main() {
int n;
std::string s;
std::cin >> n >> s;
std::cout << dfs(s) << char(10);
return 0;
}
H. Line Graph Matching
给祁神讲完题意就被秒了，只能说好强大的直感
这题乍一看很吓人，其实很容易发现对于一个有偶数条边的连通图，它的线图最后总有完美匹配
证明的话先考虑树的情况，不难发现从叶子到根贪心地匹配即可，然后推广到图也亦然成立
否则若图有偶数条边，需要分类讨论下，如果所选的边不是桥，则去掉这条边后剩下的部分满足上述要求，剩下的边都能全选
若选的边为桥，那么需要满足断开的两个连通块内部各有偶数条边，这个只要跑个边双缩点，把图缩成树然后DFS一下即可
最后再所有可以删除的边中选一个权值最小的删去即可，复杂度\(O(n+m)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=200005;
int n,m,x[N],y[N],z[N],ret,low[N],dfn[N],stk[N],bel[N],vis[N],sz[N],top,idx,bcc;
vector <int> v[N]; vector <pi> nv[N];
inline void Tarjan(CI now,CI pre)
{
low[now]=dfn[now]=++idx; stk[top++]=now; vis[now]=1;
for (auto to:v[now]) if (to!=pre)
{
if (!dfn[to])
{
Tarjan(to,now);
if (low[now]>low[to]) low[now]=low[to];
} else if (vis[to]&&low[now]>dfn[to]) low[now]=dfn[to];
}
if (low[now]==dfn[now])
{
++bcc; int x; do
{
x=stk[--top]; vis[x]=0; bel[x]=bcc;
} while (x!=now);
}
}
inline void DFS(CI now=1,CI fa=0)
{
for (auto [to,w]:nv[now]) if (to!=fa)
{
DFS(to,now); sz[now]+=sz[to]+1;
if (sz[to]%2==0) ret=min(ret,w);
}
}
int main()
{
// freopen("H.in","r",stdin); freopen("H.out","w",stdout);
RI i; long long sum=0; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
scanf("%d%d%d",&x[i],&y[i],&z[i]),sum+=z[i],v[x[i]].push_back(y[i]),v[y[i]].push_back(x[i]);
if (m%2==0) return printf("%lld",sum),0;
ret=1e9; for (Tarjan(1,0),i=1;i<=m;++i)
if (bel[x[i]]==bel[y[i]]) ret=min(ret,z[i]),++sz[bel[x[i]]];
else nv[bel[x[i]]].push_back(pi(bel[y[i]],z[i])),nv[bel[y[i]]].push_back(pi(bel[x[i]],z[i]));
return DFS(),printf("%lld",sum-ret),0;
}
I. Linear Fractional Transformation
什么鬼东西，题目都看不懂，但无所谓徐神会出手，这就是数理基础给我的自信
#include <bits/stdc++.h>
constexpr double eps = 1e-8;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
inline void read(int& x)
{
x=0; char ch; int flag=1; while (!isdigit(ch=tc())) if (ch=='-') flag=-1;
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag;
}
inline void read(double& rx)
{
int x=0; char ch; int flag=1; while (!isdigit(ch=tc())) if (ch=='-') flag=-1;
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc())); x*=flag; rx=x;
}
#undef tc
#undef pc
}F;
struct Complex {
double r, i;
inline Complex () {}
inline Complex (double r, double i): r(r), i(i) {}
inline Complex operator +(const Complex &b) const {
return {r + b.r, i + b.i};
}
inline Complex operator -(const Complex &b) const {
return {r - b.r, i - b.i};
}
inline Complex operator *(const Complex &b) const {
return {r * b.r - i * b.i, r * b.i + i * b.r};
}
inline Complex operator /(const Complex &b) const {
const double aa = b.r * b.r + b.i * b.i;
return {
(r * b.r + i * b.i) / aa,
(i * b.r - r * b.i) / aa
};
}
inline double len2() {
return r * r + i * i;
}
inline friend std::ostream& operator <<(std::ostream& out, const Complex &c) {
return out << c.r << ' ' << c.i;
}
};
int main() {
//freopen("I.in","r",stdin);
std::cout << std::fixed << std::setprecision(10);
int T; F.read(T); while(T--) {
Complex z1, f1, z2, f2, z3, f3, z0, y, t, m1, m2, q, p;
F.read(z1.r); F.read(z1.i); F.read(f1.r); F.read(f1.i);
F.read(z2.r); F.read(z2.i); F.read(f2.r); F.read(f2.i);
F.read(z3.r); F.read(z3.i); F.read(f3.r); F.read(f3.i);
F.read(z0.r); F.read(z0.i);
if( ( (z3 - z1) * (f2 - f1) - (z2 - z1) * (f3 - f1) ).len2() <= eps) {
Complex b = (f3 - f1) / (z3 - z1);
std::cout << f3 + b * (z0 - z3) << char(10);
continue;
}
__retry__:
y = (f1 - f2) / (f2 - f3) * (z3 - z2) / (z2 - z1) - Complex{1, 0};
if(y.len2() < eps) {
std::swap(f1, f2);
y = (f1 - f2) / (f2 - f3) * (z3 - z2) / (z2 - z1) - Complex{1, 0};
}
if(y.len2() < eps) {
std::swap(f2, f3);
goto __retry__;
}
t = (z3 - (y + Complex{1, 0}) * z1) / y;
m1 = z1 + t; m2 = z2 + t;
q = (f1 - f2) * m1 * m2 / (m2 - m1);
p = f1 - q / m1;
std::cout << p + q / (z0 + t) << char(10);
}
return 0;
}
J. Luggage Lock
很套路的爆搜题，不难发现其实状态数只有\(10^4\)种，同时每个状态的转移也只有\(20\)种，因此可以大力BFS
但由于询问组数较多，直接每次重新做肯定会T，但仔细一想会发现其实我们可以把起点统一归到\(0000\)，然后把终点归到两个串的差值，这样固定了起点后就可以\(O(1)\)回答询问了
#include<cstdio>
#include<iostream>
#include<queue>
#include<array>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
const int S=10005,s[10]={1,2,4,8,3,6,12,7,14,15};
int t,dis[S]; char A[10],B[10];
inline void inc(int& x,CI y)
{
if ((x+=y)>=10) x-=10;
}
int main()
{
//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
auto trs=[&](const array <int,4>& it)
{
return it[0]*1000+it[1]*100+it[2]*10+it[3];
};
RI i,j,k; memset(dis,-1,sizeof(dis));
queue <array <int,4>> q; dis[trs({0,0,0,0})]=0; q.push({0,0,0,0});
while (!q.empty())
{
auto now=q.front(); q.pop(); int d=dis[trs(now)];
for (i=0;i<10;++i)
{
auto nxt=now; for (j=0;j<4;++j) if ((s[i]>>j)&1) inc(nxt[j],1);
if (!~dis[trs(nxt)]) dis[trs(nxt)]=d+1,q.push(nxt);
nxt=now; for (j=0;j<4;++j) if ((s[i]>>j)&1) inc(nxt[j],9);
if (!~dis[trs(nxt)]) dis[trs(nxt)]=d+1,q.push(nxt);
}
}
for (scanf("%d",&t);t;--t)
{
scanf("%s%s",A,B); array <int,4> a,b;
for (i=0;i<4;++i) a[i]=A[i]-'0',b[i]=B[i]-'0';
/*int ans=1e9; for (i=0;i<16;++i)
{
array <int,4> it; for (j=0;j<4;++j)
{
it[j]=(b[j]-a[j]+10)%10;
if ((i>>j)&1) it[j]=(10-it[j])%10;
}
printf("[%d %d %d %d] : %d\n",it[0],it[1],it[2],it[3],dis[trs(it)]);
ans=min(ans,dis[trs(it)]);
}*/
array <int,4> it; for (i=0;i<4;++i) it[i]=(b[i]-a[i]+10)%10;
printf("%d\n",dis[trs(it)]);
}
return 0;
}
K. Matrix Operations
本来还在吐槽这场怎么没有DS题，好家伙最后看到这个题我人直接傻了，做不了一点
L. Perfect Matchings
很经典的一个题，想到容斥的话就很套路了
首先不难发现我们只要对树上的点进行匹配，只要一个方案满足匹配的两点在树上没有边直接相连最后一定能在图上找到一个对应的方案
直接以这个为限制来DP的话会很难处理，因为某个点的不同子树内的点可以任意合并，就完全没法处理了
因此需要换个角度，考虑这种每条边都不选的东西，很容易想到用容斥来转化
不妨设最后在树上选了恰好\(k\)条树边的方案数为\(F(k)\)，\(2x\)个点自由匹配的方案数为\(G(2x)\)
则最后的答案就是\(\sum F(k)\times G(2n-2k)\times (-1)^k\)，其中\(G(2x)=1\times 3\times 5\times \cdots \times (2x-1)\)
考虑\(F(k)\)怎么计算，这个就很显然用树上背包了，设\(f_{i,j,0/1}\)表示处理了\(i\)的子树，其中选了\(j\)条树边，\(i\)这个点匹配/未匹配的方案数，转移显然
最后\(F(k)=f_{1,k,0}+f_{1,k,1}\)，总复杂度\(O(n^2)\)
#include<cstdio>
#include<cstring>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=4005,mod=998244353;
int n,x,y,f[N][N][2],sz[N],g[N]; vector <int> v[N];
inline void DFS(CI now=1,CI fa=0)
{
f[now][0][0]=1; sz[now]=1;
for (auto to:v[now]) if (to!=fa)
{
DFS(to,now); RI i,j; static int tmp[N][2];
for (i=0;i<=sz[now]+sz[to];++i) tmp[i][0]=tmp[i][1]=0;
for (i=0;i<=sz[now];++i) for (j=0;j<=sz[to];++j)
{
(tmp[i+j][0]+=1LL*f[now][i][0]*(f[to][j][0]+f[to][j][1])%mod)%=mod;
(tmp[i+j][1]+=1LL*f[now][i][1]*(f[to][j][0]+f[to][j][1])%mod)%=mod;
(tmp[i+j+1][1]+=1LL*f[now][i][0]*f[to][j][0]%mod)%=mod;
}
for (sz[now]+=sz[to],i=0;i<=sz[now];++i)
f[now][i][0]=tmp[i][0],f[now][i][1]=tmp[i][1];
}
}
int main()
{
//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
RI i; for (scanf("%d",&n),n*=2,i=1;i<n;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (g[1]=1,i=3;i<=n;i+=2) g[i]=1LL*g[i-2]*i%mod;
int ans=0; for (DFS(),i=0;i<n;++i)
{
int cur=1LL*(f[1][i][0]+f[1][i][1])*g[max(1,n-i*2-1)]%mod;
if (i&1) ans=(ans-cur+mod)%mod; else (ans+=cur)%=mod;
}
return printf("%d",ans),0;
}
M. String Problem
String Master徐神来全秒了，直接后缀排序然后离线搞一下（徐神原话），反正我不会
#include <bits/stdc++.h>
const int $n = 1000000, $logn = 21;
int rk_base[2][$n + 1];
int sa[$n + 1], *rk = rk_base[0], *rk2 = rk_base[1], bucket[$n + 1], sa2[$n + 1];
int height[$n + 1], ST[$n + 1][$logn], STM;
int mylog2[$n + 1];
void get_sa(char *s, int n) {
int i, m = 122, d, j, *tmp, t;
for(i = 1; i <= m; ++i) bucket[i] = 0;
for(i = 1; i <= n; ++i) bucket[rk[i] = s[i]] += 1;
for(i = 2; i <= m; ++i) bucket[i] += bucket[i - 1];
for(i = 1; i <= n; ++i) sa[bucket[rk[i]]--] = i;
for(d = 1; d < n; d <<= 1) {
for(i = 0; i < d; ++i) sa2[i] = n - i;
for(i = 1, j = d; i <= n; ++i) if(sa[i] > d) sa2[j++] = sa[i] - d;
for(i = 1; i <= m; ++i) bucket[i] = 0;
for(i = 1; i <= n; ++i) bucket[rk[i]] += 1;
for(i = 2; i <= m; ++i) bucket[i] += bucket[i - 1];
for(i = n - 1; ~i; --i) sa[bucket[rk[sa2[i]]]--] = sa2[i];
rk2[sa[1]] = 1;
for(i = 2; i <= n; ++i) rk2[sa[i]] = rk2[sa[i - 1]] + \
(rk[sa[i]] != rk[sa[i - 1]] || rk[sa[i] + d] != rk[sa[i - 1] + d]);
tmp = rk, rk = rk2, rk2 = tmp;
m = rk[sa[n]]; if(m == n) break;
}
for(i = 1, j = 0; i <= n; ++i) {
if(j) j -= 1;
while(s[i + j] == s[sa[rk[i] - 1] + j]) j += 1;
height[rk[i]] = j;
}
for(i = 1; i <= n; ++i) ST[i][0] = height[i];
for(i = 1, t = 2; t < n; ++i, t <<= 1)
for(j = 1; j + t <= n + 1; ++j)
ST[j][i] = std::min(ST[j][i - 1], ST[j + (t >> 1)][i - 1]);
STM = i - 1;
mylog2[1] = 0;
for(i = 2; i < n; ++i) mylog2[i] = mylog2[i >> 1] + 1;
return ;
}
int lcp(int a, int b) {
a = rk[a], b = rk[b];
if(a > b) std::swap(a, b);
a += 1;
int tmp = mylog2[b - a + 1];
return std::min(ST[a][tmp], ST[b - (1 << tmp) + 1][tmp]);
}
int n;
char s[$n + 2];
using pii = std::pair<int, int>;
std::priority_queue<pii, std::vector<pii>, std::greater<pii> > eventQ;
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
get_sa(s, n);
int maxSuf = 1;
printf("1 1\n");
for(int i = 2; i <= n; ++i) {
while(eventQ.size() && eventQ.top().first <= i) {
if(rk[eventQ.top().second] > rk[maxSuf])
maxSuf = eventQ.top().second;
eventQ.pop();
}
if(rk[i] < rk[maxSuf]);
else
if(s[i] > s[maxSuf]) maxSuf = i;
else eventQ.push({i + lcp(i, maxSuf), i});
printf("%d %d\n", maxSuf, i);
}
return 0;
}
Postscript
今天晚上就要夜袭合肥了，希望第一次ICPC能有个不错的结果吧（别再打银了，要拿银牌大满贯了）
标签：std,now,const,Contest,int,Shenyang,include,Regional,define From： https://www.cnblogs.com/cjjsb/p/17853036.html