Preface
最害怕的一集，徐神感冒身体不适只能口胡前半场，祁神中途也有事下机导致一段时间内只有我一个人在写题
最后也是不负众望体现出没有队友我究竟是多么地彩笔，后面也索性开摆了直接后面3h梭哈写H题（主要写个假做法浪费很长时间）最后喜被卡常
打完这场特意叫了一天休息，一是为了徐神恢复身体，二是为了补一补这场剩下没写的可做题
A. Archeologists
思博题，比赛的时候感觉很像个模拟费用流但就是流不来，后面一看果然是这玩意
首先考虑一个转化，对\(\{1,2,\cdots,n\}\)上的位置做线段覆盖，要求端点必须是整点，且每个点作为左右端点至多一次
设\(i\)点被覆盖的次数为\(c_i\)，则最后的答案为\(\sum c_i\times p_i\)
对原数组求出前缀和\(s_i\)后转化为在\(\{0,1,2,\cdots,n\}\)上选择\(n+1\)个区间，左端点对应的位置为减，右端点对应的位置为加，求最大权值
考虑用一个费用流模型来刻画，首先\(i\to i+1\)连容量\(\infty\)，费用为\(0\)的边，然后\(S\to i\)连容量\(1\)，费用为\(-s_i\)的边；\(i\to T\)连容量\(1\)，费用为\(s_i\)的边，其最大费用最大流就是答案
考虑模拟费用流，我们直接倒着维护，若当前点选择作为左端点，则其将匹配后缀中权值最大的出边；否则将其作为右端点加入待选中
注意到还需实现反悔过程，这题中因为\(a\to b,b\to c\)等价于\(a\to c\)，因此选该点做左端点时也要将\(s_i\)加入待选中以实现反悔（退流）操作
用大根堆维护待选的出边，总复杂度\(O(n\log n)\)
#include<cstdio>
#include<iostream>
#include<queue>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=250005;
int n,p[N],pfx[N],ans; priority_queue <int> hp;
signed main()
{
RI i; for (scanf("%lld",&n),i=1;i<=n;++i)
scanf("%lld",&p[i]),pfx[i]=pfx[i-1]+p[i];
for (hp.push(pfx[n]),i=n-1;i>=0;--i)
{
if (hp.top()-pfx[i]>0) ans+=hp.top()-pfx[i],hp.pop(),hp.push(pfx[i]);
hp.push(pfx[i]);
}
return printf("%lld",ans),0;
}
B. Reverse Game
差点被签到题腐乳，还好祁神发现了操作的本质
考虑翻转10会让原序列的逆序对减少\(1\)，而其它三种操作均会让逆序对减少\(2\)
同时不难发现如果可以进行后面三种操作，也一定能进行第一种操作
因此问题转化为有一堆石子，两人轮流取，每次取\(1,2\)颗，问谁必胜
这是个经典的Bash博弈模型，按照初始状态的逆序对数量对\(3\)的余数判断即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
string str;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> str;
int n = str.length();
int cnt0=0;
int res=0;
for (int i=n-1; i>=0; --i){
if (str[i]=='1') res+=cnt0;
else ++cnt0;
}
if (res%3==0) cout << "Bob\n";
else cout << "Alice\n";
return 0;
}
C. 3-colorings
哈人，还有题答，鉴定为做不了一点
D. Disk Sort
比赛时候没仔细想，提出了正确的做法但感觉不对（其实是懒得写），赛后写了下发现也不难写
考虑进行\(n-1\)轮，每次将一种颜色复原并保证该轮后仍存在一根空的柱子（\(n-1\)轮后最后一种颜色会自动复原）
那么只要保证每一轮至多进行\(6\)次操作，最后的操作总数就是\(6(n-1)+3=6n-3<6n\)，符合题意
考虑我们把层数从上到下标为\(0,1,2\)，那么考虑对某种颜色，其高度分布记为\((a,b,c)\)，不妨设\(a\le b\le c\)
直觉告诉我们先恢复更靠近上层的颜色盘总是最优的，同时根据抽屉原理，总存在某个颜色的盘满足\(a+b+c\le 3\)
然后手玩一下所有情况会发现绝大多数都可以在\(6\)轮之内完成，但只有\((1,1,1)\)的情况除外
但再仔细分析一波会发现总存在一种颜色，使得其存在一个处于第\(0\)层的盘面，并且另外两个盘面不同时位于第\(2\)层，对于这种情况我们总能做到\(6\)步之内的操作
实现的话可以从上往下依次归位，但要注意操作的盘在同一柱子上的一些细节，具体看代码
#include<cstdio>
#include<iostream>
#include<deque>
#include<vector>
#include<algorithm>
#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=1005;
int n,x; deque <int> s[N]; vector <pi> pos[N]; vector <pi> ans;
inline void move(CI x,CI y)
{
ans.push_back(pi(x,y));
int v=s[x].front(); pi it=pi(3-s[x].size(),x); s[x].pop_front();
for (RI i=0;i<pos[v].size();++i) if (pos[v][i]==it)
{
pos[v].erase(pos[v].begin()+i); break;
}
pos[v].push_back(pi(2-s[y].size(),y)); s[y].push_front(v);
}
int main()
{
RI i,j; for (scanf("%d",&n),i=0;i<3;++i)
for (j=1;j<=n;++j) scanf("%d",&x),s[j].push_back(x),pos[x].push_back(pi(i,j));
for (;;)
{
int tar=-1,col=-1;
for (i=1;i<=n+1;++i) if (s[i].empty()) { tar=i; break; }
for (i=1;i<=n;++i)
{
if (pos[i][0].se==pos[i][1].se&&pos[i][0].se==pos[i][2].se) continue;
sort(pos[i].begin(),pos[i].end());
if (pos[i][0].fi==1||pos[i][0].fi+pos[i][1].fi+pos[i][2].fi>3) continue;
col=i; break;
}
if (col==-1) break; vector <int> spare;
vector <pi> tmp=pos[col];
for (i=0;i<3;++i)
{
int idx=tmp[i].se;
while (s[idx].front()!=col)
{
for (j=0;j<spare.size();++j)
if (idx!=spare[j])
{
move(idx,spare[j]); spare.erase(spare.begin()+j);
spare.push_back(idx); break;
}
}
move(idx,tar); spare.push_back(idx);
}
int mn=4,num=-1; for (i=1;i<=n+1;++i) if (s[i].size()<mn) mn=s[i].size(),num=i;
while (!s[num].empty())
{
int unfull=-1; for (i=1;i<=n+1;++i)
if (i!=num&&s[i].size()<3) { unfull=i; break; }
move(num,unfull);
}
}
if (!s[n+1].empty())
{
int tar=-1; for (i=1;i<=n;++i) if (s[i].empty()) { tar=i; break; }
while (!s[n+1].empty()) move(n+1,tar);
}
printf("%d\n",ans.size());
for (auto [x,y]:ans) printf("%d %d\n",x,y);
return 0;
}
E. Divisible by 3
大力出奇迹，手玩所有Case找到规律直接艹过
先将所有数\(\bmod 3\)，考虑对于一个区间，其中\(0\)的个数显然没有影响，不妨设其中\(1,2\)的个数各有\(x,y\)个
推个贡献的式子然后大力分讨一下最后贡献是\(3\)的倍数的情况，发现当且仅当\((x\bmod 3,y\bmod 3)=(0,0),(0,1),(1,0)\)时成立，拿个前缀和维护一下即可
#include<cstdio>
#include<iostream>
#include<cstring>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=500005,d1[3]={0,0,1},d2[3]={0,1,0};
int n,a[N],bkt[3][3],cur1,cur2,ans;
signed main()
{
RI i,j; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),a[i]%=3;
for (++bkt[cur1=0][cur2=0],i=1;i<=n;++i)
{
cur1+=(a[i]==1); cur2+=(a[i]==2); cur1%=3; cur2%=3;
for (j=0;j<3;++j)
{
int pre1=(cur1-d1[j]+3)%3,pre2=(cur2-d2[j]+3)%3;
ans+=bkt[pre1][pre2];
}
++bkt[cur1][cur2];
}
return printf("%lld",ans),0;
}
F. Fence Job
首先考虑转化题意，对于每个位置\(i\)求出\(h_i\)为最小值的极长区间，记为\([l_i,r_i]\)，则可以看作每个数可以对\([l_i,r_i]\)任意赋值
然后直接大力DP，设\(f_{i,j}\)表示考虑了前\(i\)个位置，最后的序列确定了\(j\)个元素的方案数
若选择第\(i\)个位置不确定最终序列，则\(f_{i,j}\leftarrow f_{i-1,j}\)，否则有：
\[f_{i,j}\leftarrow\sum_{k=l_i-1}^j f_{i-1,k}\ \ \ (j\in[l_i,r_i]) \]拿个前缀和优化一下即可做到\(O(n^2)\)
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=3005,mod=1e9+7;
int n,a[N],l[N],r[N],f[N][N],g[N][N];
int main()
{
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i)
{
for (l[i]=1,j=i-1;j>=1;--j) if (a[j]<a[i]) { l[i]=j+1; break; }
for (r[i]=n,j=i+1;j<=n;++j) if (a[j]<a[i]) { r[i]=j-1; break; }
}
//for (i=1;i<=n;++i) printf("(%d,%d)\n",l[i],r[i]);
for (f[0][0]=g[0][0]=1,i=1;i<=n;++i) g[0][i]=1;
for (i=1;i<=n;++i)
{
for (j=0;j<=n;++j) f[i][j]=f[i-1][j];
for (j=l[i];j<=r[i];++j) if (l[i]-1<=j)
f[i][j]=(g[i-1][j]-(l[i]-2>=0?g[i-1][l[i]-2]:0)+mod)%mod;
for (g[i][0]=f[i][0],j=1;j<=n;++j) g[i][j]=(g[i][j-1]+f[i][j])%mod;
}
return printf("%d",f[n][n]),0;
}
G. Simple Hull
题目没看，弃疗
H. AND = OR
最害怕的一题，写+对拍了2h才发现做法假了，直接心态爆炸
因为AND操作总会让数变小，OR操作总会让数变大，因此可以将所有数升序排序后，枚举分界点，前半部分或起来，后半部分与起来
然后刚开始以为这个是可二分的，写了个二分答案+归并树查询的做法，不仅三个\(\log\)复杂度爆炸，还WA到天上去了
后面又冷静思考了一波发现，上面的操作并没有太多利用位运算的特性，其实两个操作的性质对于另一个刻画指标也是成立的，就是某个数二进制下\(1\)的个数
具体地，我们枚举分界点\(k\)，钦定二进制下\(1\)的个数\(<k\)的都用或操作，\(>k\)的都用与操作，若\(=k\)的数有多个则一定无解，否则\(=k\)的数可以任意选择加入哪个集合中
直接开\(30\)棵线段树，每棵线段树维护区间AND、OR，以及区间内所有数是否相同（相同的话维护个数）即可
总复杂度\(O(n\log n\log a_i)\)，但由于我写的时候为了维护边界情况用了常数极大的写法，最后成功被卡常
（以下代码交上去会TLE，但和能通过的代码对拍过正确性没有问题）
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=(1<<30)-1;
struct ifo
{
int same,val,cnt;
inline ifo(CI S=1,CI V=-1,CI C=0)
{
same=S; val=V; cnt=C;
}
friend inline ifo operator + (const ifo& A,const ifo& B)
{
if (A.val==-1) return B; if (B.val==-1) return A;
if (A.same==0||B.same==0) return ifo(0,0,0);
if (A.val!=B.val) return ifo(0,0,0);
return ifo(1,A.val,A.cnt+B.cnt);
}
};
struct num
{
int val,ext;
inline num(CI V=-1,CI E=0)
{
val=V; ext=E;
}
friend inline num operator | (const num& A,const num& B)
{
return num(A.val|B.val,A.ext|B.ext);
}
friend inline num operator & (const num& A,const num& B)
{
return num(A.val&B.val,A.ext|B.ext);
}
};
int n,q,a[N],l,r;
class Segment_Tree
{
private:
ifo O[N<<2]; num OR[N<<2],AND[N<<2];
public:
#define TN CI now=1,CI l=1,CI r=n
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void init(void)
{
for (RI i=1;i<=(n<<2);++i) OR[i]=num(0,0),AND[i]=num(INF,0),O[i]=ifo();
}
inline void updata(CI pos,CI mv,TN)
{
if (l==r)
{
OR[now]=AND[now]=num(mv,1); O[now]=ifo(1,mv,1); return;
}
int mid=l+r>>1; if (pos<=mid) updata(pos,mv,LS); else updata(pos,mv,RS);
OR[now]=OR[now<<1]|OR[now<<1|1];
AND[now]=AND[now<<1]&AND[now<<1|1];
O[now]=O[now<<1]+O[now<<1|1];
}
inline num query_or(CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return OR[now]; int mid=l+r>>1; num ret=num(0,0);
if (beg<=mid) ret=ret|query_or(beg,end,LS); if (end>mid) ret=ret|query_or(beg,end,RS); return ret;
}
inline num query_and(CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return AND[now]; int mid=l+r>>1; num ret=num(INF,0);
if (beg<=mid) ret=ret&query_and(beg,end,LS); if (end>mid) ret=ret&query_and(beg,end,RS); return ret;
}
inline ifo query_ifo(CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return O[now]; int mid=l+r>>1; ifo ret=ifo();
if (beg<=mid) ret=ret+query_ifo(beg,end,LS); if (end>mid) ret=ret+query_ifo(beg,end,RS); return ret;
}
#undef TN
#undef LS
#undef RS
}SEG[31];
int main()
{
//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
RI i; for (scanf("%d%d",&n,&q),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=0;i<=30;++i) SEG[i].init();
for (i=1;i<=n;++i) SEG[__builtin_popcount(a[i])].updata(i,a[i]);
for (;q;--q)
{
scanf("%d%d",&l,&r); static num pre[31],suf[31];
for (i=0;i<=30;++i) pre[i]=SEG[i].query_or(l,r),suf[i]=SEG[i].query_and(l,r);
for (i=1;i<=30;++i) pre[i]=pre[i]|pre[i-1];
for (i=29;i>=0;--i) suf[i]=suf[i]&suf[i+1];
int flag=0; for (i=0;i<=30&&!flag;++i)
{
ifo it=SEG[i].query_ifo(l,r); if (it.same==0) continue;
num OR=(i>0?pre[i-1]:num(0,0)),AND=(i<30?suf[i+1]:num(INF,0));
for (RI u=0;u<=min(it.cnt,2);++u)
{
int v=min(it.cnt-u,2); int Or=OR.val,And=AND.val;
if (OR.ext==0&&u==0) continue;
if (AND.ext==0&&v==0) continue;
if (u) Or|=it.val; if (v) And&=it.val;
if (Or==And) { flag=1; break; }
}
}
puts(flag?"YES":"NO");
}
return 0;
}
I. Modulo Permutations
经典看到数数题就扔给队友，然后昨天只有祁神一个人想这个题然后也犯病了
首先由于\(1,2\)怎么放都合法，因此放在最后考虑，先把\(3\sim n\)的数确定下来
考虑从大到小放数，\(f_{i,j}\)代表当前分出来的两个部分的各自最小的数
如果当前放的是\(x\)，可以直接从\(f_{x+1,j}\)转移到\(f_{x,j}\)；否则如果\(j\bmod x\le 2\)，可以从\(f_{x+1,j}\)转移到\(f_{x,x+1}\)
手玩一下发现可以压掉一维，同时满足上述转移的第二种情况的数是有倍数关系的，直接做复杂度就是调和级数的
总复杂度\(O(n\log n)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
void add(int &x, int a){if ((x+=a)>=MOD) x-=MOD;}
const int N = 1e6+5;
int f[N];
signed main(){
int n; cin >> n;
if (1==n) cout << "1\n";
else if (2==n) cout << "2\n";
else{
for (int x=n-1; x>=3; --x){
f[x+1]=1;
for (int i=1; i*x<=n; ++i){
for (int j=0; j<=2; ++j){
if (i*x+j<=x+1 || i*x+j>n) continue;
add(f[x+1], f[i*x+j]);
}
}
}
int ans=1;
for (int i=4; i<=n; ++i) add(ans, f[i]);
// printf("ans=%lld\n", ans);
cout << ans*2%MOD*n%MOD << '\n';
}
return 0;
}
J. One Piece
感觉是个可做题，但还没太搞懂先弃了
K. Codenames
放AK题，鉴定为寄
L. Neo-Robin Hood
这题其实基本还是徐神教的，不敢想象如果真的没有徐神要被打成啥样
首先根据上次VP的那场的某个题的思路，考虑对于偷\(i\)买\(j\)这个操作，它相比于偷\(j\)买\(i\)这个操作更优时一定满足\(m_i-p_j>m_j-p_i\)，即\(m_i+p_i>m_j+p_j\)
因此我们按照\(m_i+p_i\)从大到小排序后，不难发现偷的一定是一段前缀，而买的一定是一段与之不相交的后缀
如果直接枚举分界点，还是不太好处理问题，但如果加上两边各要选多少个数后就很简单了
因此想到二分答案，枚举分界点后用堆快速维护两边选若干个数的代价，总复杂度\(O(n\log^2 n)\)
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
struct ifo
{
int m,p;
friend inline bool operator < (const ifo& A,const ifo& B)
{
return A.m+A.p>B.m+B.p;
}
}a[N]; int n;
inline bool check(CI k)
{
RI i; static int pre[N],suf[N];
priority_queue <int,vector <int>,greater <int>> sml;
for (pre[0]=0,i=1;i<=k;++i) pre[i]=pre[i-1]+a[i].m,sml.push(a[i].m);
for (i=k+1;i<=n;++i) sml.push(a[i].m),pre[i]=pre[i-1]+a[i].m-sml.top(),sml.pop();
priority_queue <int> big;
for (suf[n+1]=0,i=1;i<=k;++i) suf[n-i+1]=suf[n-i+2]+a[n-i+1].p,big.push(a[n-i+1].p);
for (i=k+1;i<=n;++i) big.push(a[n-i+1].p),suf[n-i+1]=suf[n-i+2]+a[n-i+1].p-big.top(),big.pop();
for (i=k;n-i>=k;++i) if (pre[i]>=suf[i+1]) return 1;
return 0;
}
signed main()
{
RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i].m);
for (i=1;i<=n;++i) scanf("%lld",&a[i].p); sort(a+1,a+n+1);
int l=1,r=n/2,mid,ret=0; while (l<=r)
if (check(mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
return printf("%lld",ret),0;
}
M. Mistake
不难发现将每个数第一次出现归为一组，第二次出现归为一组，以此类推，如果这样都无解那么其它方案一定也无解
因此这题输入的图限制其实是假的，就是个纯纯的诈骗题
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, k, m;
int cnt[N], ans[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k >> m;
for (int i=1; i<=m; ++i){
int a, b; cin >> a >> b;
}
for (int i=1; i<=n*k; ++i){
int a; cin >> a;
++cnt[a];
ans[i] = cnt[a];
}
for (int i=1; i<=n*k; ++i) cout << ans[i] << ' ';
cout << '\n';
return 0;
}
Postscript
徐神是我们的红太阳，没有他我们都不能活
标签：const,SEERC,Contest,int,ret,2020,include,RI,define From： https://www.cnblogs.com/cjjsb/p/17975530