Codeforces Round 1299 简要题解

A.Anu Has a Function

略

B.Aerodynamic

略

C.Water Balance

vp的时候猜了一下结论，答案满足每个位置被操作恰好一次，那么显然就是对$(i,{\sum }_{j=1}^i{a}_j)$的下凸壳上相邻两个点间操作即可，建出下凸壳就做完了。
vp完后看了一下题解的证明，挺有意思的。
最小化$a_i$的字典序等价于最小化$p_i={\sum }_{j=1}^i{a}_j$的字典序。同样把$(i,p_i)$画在平面上，令每个点那么每次操作$[l,r]$相当于对$?l\le i\le r,p_i=p_{l?1}+\frac{p_r?p_{l?1}}{r?l+1}$，也就是说把$(l,p_l)?(r,p_r)$替换为线段$((l?1,p_l),(r,p_r))$对应整数横坐标上的点。注意到不论我们如何操作，任意时刻$(i,p_i)$显然都会在初始的下凸壳上方（因为每次连接了两个下凸壳上方的点），那么显然直接操作为下凸壳就是最优的。
时间复杂度为$\mathcal{O}(n)$。

#include <bits/stdc++.h>
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef double db;
typedef pair<ll,ll> pr;struct Point {
    ll x,y;Point() {
    }Point(ll a,ll b):x(a),y(b) {
    }Point operator - (Point b) {
    return Point(x-b.x,y-b.y);}
};ll cross(Point x,Point y) {
    return x.x*y.y-x.y*y.x;
}Point st[1000005];
int top;void insert(Point p) {
    while (top>1&&cross(p-st[top],st[top]-st[top-1])>=0) top--;st[++top]=p;
}int main() {
    int n;scanf("%d",&n);ll s=0;insert(Point(0,0));for(int i=1;i<=n;i++) {
    int x;scanf("%d",&x);s+=x;insert(Point(i,s));}for(int i=2;i<=top;i++) {
    db v=(db)(st[i].y-st[i-1].y)/(st[i].x-st[i-1].x);for(int j=st[i-1].x+1;j<=st[i].x;j++)printf("%.10f\n",v);}return 0;
}

D. Around the World

题目中的异或可以理解为线性空间${\mathbb{Z}}_2^5$下的加法。考虑删去所有与$1$号点相连的边，得到若干个连通分量。
对于某个连通分量，若最终它仍与$1$号点连通，那么根据一个经典的结论，在这个连通分量$(V,E)$的内部的每个非平凡回路权值组成的线性子空间可以表示为$|E|?|V|+1$个向量的张成。具体的，取出一棵内部的生成树，那么每条非树边的向量与对应树上路径向量的和就构成了这样一组向量。显然，如果这组向量线性相关，必然不能让这个连通分量与$1$号点连通。
注意到题目的限制其实保证了每个连通分量最多与$1$号点有两条相连的边。考虑同时保留这两条边，那么存在从$1$号点出发和回到$1$号点用的边不同的情况，此时相当于多了一个向量。
现在考虑合并不同连通分量的答案，显然我们要求每个连通分量对应的线性子空间的和是直和。注意到${\mathbb{Z}}_2^5$的不同线性子空间只有$374$个，我们可以考虑预处理出任意两个线性子空间是否有交以及它们的直和。这样就可以DP了，设$F[i][S]$表示考虑了前$i$个连通分量，此时所有线性子空间的直和为$S$，转移枚举这个连通分量与$1$号点的连边情况即可。
预处理可以直接bfs出所有可能的线性子空间，然后暴力枚举两个算。时间复杂度为$\mathcal{O}(nS+m+S^2?(5^2+\log S))$，其中$S=374$。

#include <bits/stdc++.h>
#define FR first
#define SE second
#define MOD 1000000007using namespace std;typedef long long ll;
typedef pair<int,int> pr;inline void add(int &x,int y) {
    ((x+=y)>=MOD)?x-=MOD:0;
}struct LB {
    int num[5];LB() {
    memset(num,0,sizeof(num));}LB(vector<int> vt) {
    for(int i=0;i<=4;i++) num[i]=vt[i];
}bool insert(int x) {
    for(int i=4;i>=0;i--)if ((x>>i)&1) {
    if (!num[i]) {
    num[i]=x;return 1;}else x^=num[i];}return 0;
}vector<int> decide() {
    vector<int> vt;vt.resize(5);for(int i=4;i>=0;i--)for(int j=i+1;j<=4;j++)if ((num[j]>>i)&1) num[j]^=num[i];for(int i=0;i<=4;i++)if (num[i]) vt[i]=num[i];return vt;
}};queue <vector<int> > q;
int trans[400][400],cnt;vector <int> vt[400];
LB a[400];
map <vector<int>,int> mp;void pre() {
    vector<int> vt;vt.resize(5);mp[vt]=++cnt;a[1]=LB(vt);q.push(vt);while (!q.empty()) {
    vector<int> t=q.front();q.pop();for(int i=0;i<32;i++) {
    LB cur(t);if (cur.insert(i)) {
    vector<int> curv=cur.decide();if (mp.count(curv)) continue;mp[curv]=++cnt;a[cnt]=LB(curv);q.push(curv);}}}for(int i=1;i<=cnt;i++)for(int j=1;j<=i;j++) {
    LB u=a[i],v=a[j];bool ok=1;for(int k=0;k<=4;k++)if (v.num[k]) {
    if (!u.insert(v.num[k])) {
    ok=0;break;}}if (ok) trans[i][j]=trans[j][i]=mp[u.decide()];}
}vector <pr> e[100005];bool vis[100005];
int dis[100005],dep[100005];LB curv;
bool be0;
pr to1[2];
int sz;void dfs(int x,int fa) {
    vis[x]=1;for(int i=0;i<e[x].size();i++) {
    int u=e[x][i].FR,v=e[x][i].SE;if (u==1) to1[sz++]=pr(x,v);else if (!vis[u]) {
    dis[u]=dis[x]^v;dep[u]=dep[x]+1;dfs(u,x);} else if (u!=fa&&dep[u]<dep[x]) {
    if (!curv.insert(v^dis[x]^dis[u])) be0=1;}}
}int f[2][400],cur;void solve(int rt) {
    curv=LB();sz=be0=0;dfs(rt,0);if (!sz||be0) return;cur^=1;memcpy(f[cur],f[cur^1],sizeof(f[cur]));int id=mp[curv.decide()];for(int i=1;i<=cnt;i++)if (f[cur^1][i]&&trans[i][id]) {
    add(f[cur][trans[i][id]],f[cur^1][i]);if (sz==2) add(f[cur][trans[i][id]],f[cur^1][i]);}if (sz<2) return;if (!curv.insert(to1[0].SE^to1[1].SE^dis[to1[0].FR]^dis[to1[1].FR])) return;id=mp[curv.decide()];for(int i=1;i<=cnt;i++)if (f[cur^1][i]&&trans[i][id]) add(f[cur][trans[i][id]],f[cur^1][i]);
}int main() {
    pre();int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {
    int x,y,z;scanf("%d%d%d",&x,&y,&z);e[x].push_back(pr(y,z));e[y].push_back(pr(x,z));}cur=0;f[cur][1]=1;for(int i=2;i<=n;i++)if (!vis[i]) solve(i);int ans=0;for(int i=1;i<=cnt;i++) add(ans,f[cur][i]);printf("%d\n",ans);return 0;
}

E. So Mean

考虑${\sum }_{i=1}^{n}i\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}(n?1))$，于是我们枚举所有的$n?1$元子集，必然恰有两个答案为$1$，它们即为$1$和$n$。
注意到由于$[p_1,p_2,...,p_n]$与$[n?p_1+1,n?p_2+1,...,n?p_n+1]$无法区分，因此我们可以随便假设$1$和$n$的顺序，这样由于$1$和$n$的奇偶性不同，就可以区分$k$和$n?k+1$了。
用类似的方法，如果我们已经知道了$1?k$和$n?k+1?n$的位置，那么询问所有剩下的$n?2k?1$元子集，再按奇偶性区分即可知道$k+1$和$n?k$的位置了。但是这样需要的询问次数是$\mathcal{O}(n^2)$的，显然不能通过。
考虑只问出$1?4$和$n?3?n$的位置，然后问出剩下每个位置的数分别$\mathrm{m}\mathrm{o}\mathrm{d}3,5,7,8$的值，就可以唯一确定每个位置的数了。
注意到用$1?4$和$n?3?n$中的大小为$p?1$的所有子集可以得到$\mathrm{m}\mathrm{o}\mathrm{d}p=3,5,7$的至少$p?1$个不同的余数，那么我们显然对一个$p$有一个${\sum }_{i=2}^p\frac{i}{p}?n$的做法。
对于$8$，我们可以先问出每个位置$\mathrm{m}\mathrm{o}\mathrm{d}2$的值，再问出$\mathrm{m}\mathrm{o}\mathrm{d}4$的值，再问出$\mathrm{m}\mathrm{o}\mathrm{d}8$的值。以知道$\mathrm{m}\mathrm{o}\mathrm{d}4$的值问$\mathrm{m}\mathrm{o}\mathrm{d}8$的值为例，显然只用对某个特定的$v$，在$v$和$(v+4)\mathrm{m}\mathrm{o}\mathrm{d}8$中确定一个，注意到我们用$1?4$和$n?3?n$中的大小为$7$的所有子集至少可以凑出$\mathrm{m}\mathrm{o}\mathrm{d}8$意义下连续的$4$个数，也就是说$?v$和$?(v+4)\mathrm{m}\mathrm{o}\mathrm{d}8$至少能凑出一个，这样就可以直接问了。
时间复杂度为$\mathcal{O}(n^2)$。

#include <bits/stdc++.h>
#define FR first
#define SE secondusing namespace std;typedef pair<int,int> pr;//int perm[1005];bool ask(vector<int> vt) {
    printf("? %d ",(int)vt.size());for(int i=0;i<vt.size();i++) printf("%d ",vt[i]);printf("\n");fflush(stdout);int x;scanf("%d",&x);return x;/*int k=vt.size(),s=0;for(int i=0;i<k;i++) s+=perm[vt[i]];return s%k==0; */
}int id[3][5][7][8],ans[1005];
pr num[10];vector<int> vt[10];
bool vis1[10];void dfs(int s1,int s2,int p,int d,vector<int> q) {
    if (s1==p-1) {
    if (!vis1[s2]) {
    vis1[s2]=1;vt[s2]=q;}return;}if (d>8) return;dfs(s1,s2,p,d+1,q);q.push_back(num[d].SE);dfs(s1+1,(s2+num[d].FR)%p,p,d+1,q);
}bool vis2[1005];
int val[1005][4];void solve_prime(int n,int p,int d) {
    memset(vis1,0,sizeof(vis1));dfs(0,0,p,1,vector<int>());memset(vis2,0,sizeof(vis2));for(int i=0;i<p-1;i++)for(int j=1;j<=n;j++)if (!vis2[j]&&!ans[j]) {
    vector<int> cur=vt[(p-i)%p];cur.push_back(j);if (ask(cur)) {
    vis2[j]=1;val[j][d]=i;}}for(int i=1;i<=n;i++)if (!vis2[i]&&!ans[i]) val[i][d]=p-1;
}void solve_8(int n) {
    memset(vis1,0,sizeof(vis1));dfs(0,0,2,1,vector<int>());for(int i=1;i<=n;i++) {
    if (ans[i]) continue;int v=val[i][3];if (vis1[(2-v)%2]) {
    vector<int> cur=vt[(2-v)%2];cur.push_back(i);if (ask(cur)) val[i][3]=v; else val[i][3]=v+1;}else {
    v+=1;vector<int> cur=vt[(2-v)%2];cur.push_back(i);if (ask(cur)) val[i][3]=v; else val[i][3]=v-1;}}memset(vis1,0,sizeof(vis1));dfs(0,0,4,1,vector<int>());for(int i=1;i<=n;i++) {
    if (ans[i]) continue;int v=val[i][3];if (vis1[(4-v)%4]) {
    vector<int> cur=vt[(4-v)%4];cur.push_back(i);if (ask(cur)) val[i][3]=v; else val[i][3]=v+2;}else {
    v+=2;vector<int> cur=vt[(4-v)%4];cur.push_back(i);if (ask(cur)) val[i][3]=v; else val[i][3]=v-2;}}memset(vis1,0,sizeof(vis1));dfs(0,0,8,1,vector<int>());for(int i=1;i<=n;i++) {
    if (ans[i]) continue;int v=val[i][3];if (vis1[(8-v)%8]) {
    vector<int> cur=vt[(8-v)%8];cur.push_back(i);if (ask(cur)) val[i][3]=v; else val[i][3]=v+4;}else {
    v+=4;vector<int> cur=vt[(8-v)%8];cur.push_back(i);if (ask(cur)) val[i][3]=v; else val[i][3]=v-4;}}
}int main() {
    int n;scanf("%d",&n);/*for(int i=1;i<=n;i++) perm[i]=i;random_shuffle(perm+1,perm+n+1);if (perm[1]>(n>>1)) {for(int i=1;i<=n;i++) perm[i]=n-perm[i]+1;}*/bool v=0;int fir=0;for(int i=1;i<=n;i++) {
    vector<int> cur;for(int j=1;j<=n;j++)if (j!=i) cur.push_back(j);if (ask(cur)) {
    ans[i]=((!v)?1:n);if (ans[i]==1) fir=i;v=1;}}for(int i=2;i<=(n>>1)&&i<=4;i++)for(int j=1;j<=n;j++) {
    vector<int> cur;for(int k=1;k<=n;k++)if (k!=j&&(!ans[k]||min(ans[k],n-ans[k]+1)>=i)) cur.push_back(k);if (ask(cur)) {
    cur.clear();cur.push_back(fir);cur.push_back(j);ans[j]=((ask(cur)^(i&1))?n-i+1:i);}}if (n>8) {
    int sz=0;for(int i=1;i<=n;i++)if (ans[i]) num[++sz]=pr(ans[i],i);sort(num+1,num+sz+1);solve_prime(n,3,0);solve_prime(n,5,1);solve_prime(n,7,2);solve_8(n);for(int i=1;i<=n;i++) id[i%3][i%5][i%7][i%8]=i;for(int i=1;i<=n;i++)if (!ans[i]) ans[i]=id[val[i][0]][val[i][1]][val[i][2]][val[i][3]];}if (ans[1]>(n>>1)) {
    for(int i=1;i<=n;i++) ans[i]=n-ans[i]+1;}//for(int i=1;i<=n;i++) assert(ans[i]==perm[i]);printf("! ");for(int i=1;i<=n;i++) printf("%d ",ans[i]);printf("\n");fflush(stdout);return 0;
}