Codeforces Round 779 (Div. 2)

· 题解

昨天凌晨发生了一件巨~~(好笑)~~丢人的事 整天处于呆滞状态 所以昨天咕了

D2的trie写了1H+ 人都麻了 现在只想给自己来两个大嘴巴子

页面最好刷新一下 不然有的提示直接显示出来就挺草的

B. Marin and Anti-coprime Permutation

尝试构造这个gcd的排列 发现系数是奇数的时候 必须填一个偶数

那么n%2==1的时候 偶数数量就会不够 如果n是偶数 那么位置随便 所以答案(n2)2(\frac{n}{2})^2

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
signed main() {
	auto fac=[](int x){
		long long ans=1;
		while(x>0){
			ans=ans*x%mod;
			x--;
		}
		return ans;
	};
	int tt;cin>>tt;
	while(tt--){
		int n;cin>>n;
		if(n%2==1) puts("0");
		else cout<<fac(n/2)*fac(n/2)%mod<<endl;
	}
	return 0;
}

C. Shinju and the Lost Permutation

这题我考虑c[]下降的时候傻逼了 wyl给的思路

因为一次右移最多让prefix maximum+1 所以c一次最多+1

如果下降的时候 只要不降到1 (降到1说明此时n在第一位) 那么在满足c上升都是+1上升的条件下

都是可以构造出符合条件的p的..

我比赛的时候尝试具体分析下降幅度 然后考虑p[i]和前几个大小关系 用并查集维护传递关系

只能说做题做傻了..

#include <bits/stdc++.h>
using namespace std;
int main() {
	int tt;cin>>tt;
	while(tt--){
		int n; cin>>n;
		vector<int>c(n+1);
		int now=0;
		for(int i=1;i<=n;i++) {cin>>c[i];if(c[i]==1) now=i;}
		vector<int>a;
		for(int i=now;i<=n;i++) a.push_back(c[i]);
		for(int i=1;i<now;i++) a.push_back(c[i]);
		bool flag=true;
		for(int i=1;i<n;i++){
			if(a[i]-a[i-1]>1) {flag=false;break;}
			else if(a[i]==1) {flag=false; break;}
		}
		if(now==0) puts("NO");
		else if(flag) puts("YES");
		else puts("NO");
	}
	return 0;
}

D1. 388535 (Easy Version)

给定l=0, r [0,r] 异或一个x 变换到给定的数组a[] 求x

不同的数^x得到的答案都不同

求一个x 使得a[] xor x得到的答案总和最小，既是[0,r]

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;cin>>tt;
	for(;tt;tt--){
		vector tot(17,0);
		int l,r,tem; cin>>l>>r;
		for(int i=0;i<=r;i++){
			cin>>tem;
			for(int j=0;j<17;j++) if(tem&(1<<j)) tot[j]++;
		}
		int ans=0;
		for(int i=0;i<17;i++) if(tot[i]>r+1-tot[i]) ans+=(1<<i);
		cout<<ans<<endl;
	}
	return 0;
}

D2. 388535 (Hard Version)

l没有=0的限制

D1一开始我看到异或就觉得是Trie

但是后来又sb的"专下判"觉得Trie做这个会T..

因为我想的找x是把所有的x放到Trie里面 然后所有a[i]统计一遍 然后计算每个x符合的数量 如果是r-l+1就OK

发现这个是O(N^2)的假思路

正确做法上是把a[]插入到Trie里面 然后枚举x=l xor a[i]x=l\ xor\ a[i] 找x能异或出来的最值边界 恰好是[l,r]就符合条件

然后T了 因为t组数据多测的时候memset炸时间了 看了知乎上严格鸽写的多测时候初始化Trie的方法

写的要脑淤血了 才发现我的tot计数方式是++tot 所以清空tot的时候要清空trie[tot+1][0/1] 麻了

#include<bits/stdc++.h>
using namespace std;
const int N=150010;
int l,r,trie[N*32][2],a[N],tot;
void add(int x){
	int p=0;
	for(int i=16;i>=0;i--){
		int ch=(x>>i)&1;
		if(!trie[p][ch]){
			trie[tot+1][0]=trie[tot+1][1]=0;
			trie[p][ch]=++tot;
		}
		p=trie[p][ch];
	}
}
int qryMx(int x) {
	int ans=0,p=0;
	for(int i=16;i>=0;i--){
		int ch=(x>>i)&1;
		if(trie[p][ch^1]) p=trie[p][ch^1],ans+=(1<<i);
		else p=trie[p][ch];
	}
	return ans;
}
int qryMn(int x){
	int ans=0,p=0;
	for(int i=16;i>=0;i--){
		int ch=(x>>i)&1;
		if(trie[p][ch]) p=trie[p][ch];
		else p=trie[p][ch^1],ans+=(1<<i);
	}
	return ans;
}
void solve(){
	cin>>l>>r;
	tot=0; trie[0][0]=trie[0][1]=0;
	for(int i=1;i<=r-l+1;i++){cin>>a[i],add(a[i]);}
	for(int i=1;i<=r-l+1;i++){
		int x=a[i]^l;
		if(qryMn(x)==l&&qryMx(x)==r){
			cout<<x<<endl;
			return ;
		}
	}
}
int main() {
	int tt;cin>>tt;
	while(tt--){
		solve();
	}
	return 0;
}

还有个做法是运用成对变换

如果a[i]是偶数 那么a[i]^1=a[i]+1 奇数则是-1

把[l,r] 和 a[]里面的对全部删掉 因为他们可以一一对应起来

那么如果l是奇数 l就没有匹配的东西 如果r是偶数 r没有匹配的项

这时候就可以和剩下来的a[]配对 检查一下

如果l是偶数 r是奇数 那么把所有的值缩小一倍 返回x的时候*2即可

#include <bits/stdc++.h>
using namespace std;
int solve() {
  int l, r;
  cin >> l >> r;
  vector a(r - l + 1, 0);
  set<int> s;
  for (int i = 0; i < r - l + 1; i++) {
    int tem;
    cin >> tem;
    s.insert(tem);
  }
  int f = 1;
  auto check = [&](int x) {
    for (auto it : s)
      if ((it ^ x) < l || (it ^ x) > r)
        return false;
    return true;
  };
  while (1) {
    set<int> t = s;
    for (auto it : s)
      if (t.find(it ^ 1) != t.end())
        t.erase(it ^ 1);
    if (l % 2 == 1 && r % 2 == 1)
      return f * (*t.begin() ^ l);
    if (l % 2 == 0 && r % 2 == 0)
      return f * (*t.begin() ^ r);
    if (l % 2 == 1 && r % 2 == 0) {
      if (check(*t.begin() ^ l))
        return f * (*t.begin() ^ l);
      else
        return f * (*t.begin() ^ r);
    }
    t.clear();
    for (auto it : s)
      t.insert(it / 2);
    s = t;
    l /= 2;
    r /= 2;
    f *= 2;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
		cout<< solve()<<endl;
  }
  return 0;
}

tourist这题写的DP 看不懂...

E. Gojou and Matrix Game

从起点开始 每次需要移动到一个权值更大的点 谁走到最后一步 谁就赢了 (废话..)

然后就不会了.. 没学过博弈论 不清楚是不是

题解说是DP

发现v[i][j]都是不同的 设dp[a][b]=1表示选择(a,b)的人会赢

显然如果v[a][b]=n 那么dp[a][b]=1

对于dp[i][j] = 1

if for all (i',j') ∈∣i−i′∣+∣j−j′∣>k\in |i-i'|+|j-j'|>k 都有 dp[i'][j']=0

if for all (i',j') ∈dp[i′][j′]=1\in dp[i'][j']=1 都有∣i−i′∣+∣j−j′∣<=k|i-i'|+|j-j'|<=k

那么做法就是维护一个集合S (i′,j′∣∈dp[i′][j′]=1)(i',j' | \in dp[i'][j']=1)

  1. S中加入点(i,j)
  2. 检查所有的(i',j')是否满足∣i−i′∣+∣j−j′∣<=k|i-i'|+|j-j'|<=k

这些都很容易想到，， 关键的一个trick是关于绝对值不等式的变换

∣i−i′∣+∣j−j′∣<=k  ⟺  max(∣i+j−(i′+j′)∣,∣i−j−(i′−j′)∣)≤k(1)|i-i'|+|j-j'|<=k \iff max(|i+j-(i'+j')|,|i-j-(i'-j')|)\leq k \tag{1}

当i≥i′i\geq i'时 有

∣i−i′∣+∣j−j′∣=max[i−i′+j−j′,i−i′+j′−j]=max[(i+j)−(i′+j′),(i−j)−(i′−j′)](2)|i-i'|+|j-j'|=max[i-i'+j-j',i-i'+j'-j]=max[(i+j)-(i'+j'),(i-j)-(i'-j')]\tag{2}

当i<i′i<i'时 同理 整理一下就得到了(1)(1)式

然后就好处理了.. 只要管一下最大最小的(i'+j') (i'-j') 我是呆逼..

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define il inline
#define rg register
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long ll;
typedef double db;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const int MOD=998244353;
const int mod=1e9+7;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
// head
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,k;
	cin>>n>>k;
	vector v(n,vector<int>(n));
	vector<array<int,2>>pos(n*n);
	rep(i,0,n-1){
		rep(j,0,n-1){
			cin>>v[i][j];
			v[i][j]--;
			pos[v[i][j]]={i,j};
		}
	}
	int p1=-inf,p2=-inf,p3=-inf,p4=-inf;
	vector<string>ans(n,string(n,'G'));
	per(i,0,n*n-1){
		auto [x,y]=pos[i];
		if(p1>x+y+k||p2>-x-y+k||p3>x-y+k||p4>y-x+k) continue;
		ans[x][y]='M';
		p1=max(p1,x+y);
		p2=max(p2,-x-y);
		p3=max(p3,x-y);
		p4=max(p4,y-x);
	}
	rep(i,0,n-1) cout<<ans[i]<<'\n';
}

F. Juju and Binary String

题意转化成 给定一个长为n的01串 选出最少的子区间使得0 1的数量恰好达到要求

0和1的数量求个gcd 处理一下至少的值和m是否成倍数关系 判断-1还是k 这个很好搞..

到这里我就无了，， 想了20min 没啥好的区间处理 也想不到DP怎么设

甚至想过类似环形DP的拓展空间 因为对顺序没什么要求 于是点开tutorial..

看了Hint1 就是判断m啥时候行啥时候不行 看了Hint2.. 开 幕 雷 击

We don't need more than 2 parts, or to say 𝑘≤2𝑘\leq2 is needed in this problem.

未曾设想过的道路.. 虽然想了一个情况类似前面一个1中间一堆0然后后半段01均匀分布

发现不能很贪心的取0取够 然后取1 或者说别的一些贪心思路 但是没具体算过..

设cic_i表示[i,i+m-1]内1的数量 令s[i+n]=s[i]故c[i+n]=c[i]

因为∣ci−ci−1∣≤1|c_i-c_{i-1}|\leq 1 所以 ∀y∈ [min(ci), max(ci)]\forall y\in\ [min(c_i),\ max(c_i)] 都有 c[i]=yc[i]=y

然后思考一下这个每次上升下降至多1导致的连续c[i] 和 k≤2\leq 2有什么关系 可能要感性理解(糊)一下..

题解这部分没讲清楚 这个点还是很值得思考的(在很显然的看出来之前) 评论区也有个红名smax讲的很详细了

在s[]扩展了一倍之后 有个感觉就是存在一段[i,i+m-1]的区间满足条件

证明显然是正难则反的方法

  1. ∀c[i],c[i]≤所m需要的1数量\forall c[i], c[i]\leq 所m需要的1数量
  2. ∀c[i],c[i]≥所需要的1数量\forall c[i], c[i]\geq 所需要的1数量

发现这两种都很轻松的违背mm is a multiple of ngcd(w,b)\frac{n}{gcd(w,b)}

嗯 c[i]虽然可以有大有小 但是因为单次增减变化都在1 所以恰好存在一个点满足条件

如果这个选择的范围超过了n 也就是后半段要从原s[]的前面取 那么k=2

感觉这个+-1的思想和之前的#757 最后一题很像 不过那个维护要用动态开点权值树 这个明显好写很多

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define il inline
#define rg register
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long ll;
typedef double db;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const int MOD=998244353;
const int mod=1e9+7;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
// head
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);;
	int tt; cin>>tt;
	while(tt--){
		int n,m; cin>>n>>m;
		string s; cin>>s;
		int one=count_if(all(s),[](char c){return c=='1';});
		if(1LL*one*m%n!=0) {cout<<"-1\n"; continue;}
		one=1LL*one*m/n;
		vector c(2*n+1,0);
		s="#"+s+s;
		for(int i=1;i<=m;i++) c[1]+=((s[i]=='1')?1:0);
		for(int i=2;i<=2*n-m+1;i++) {
			c[i]=c[i-1];
			if(s[i-1]=='1') c[i]--;
			if(s[i+m-1]=='1') c[i]++;
		}
		int now;
		for(int i=1;i<=2*n-m+1;i++)
			if(c[i]==one) {now=i; break;}
		if(now>n){
			cout<<"1\n";
			cout<<now%n<<' '<<(now+m-1)%n<<'\n';
		} else {
			if(now+m-1>n) {
				cout<<"2\n";
				cout<<"1 "<<m-(n-now+1)<<'\n';
				cout<<now<<' '<<n<<endl;
			} else{
				cout<<"1\n";
				cout<<now<<' '<<now+m-1<<endl;
			}
		}
	}
	return 0;
}

评论区说这是PermutationForces.. 属实是整把结论梭哈到底了

昨天的事情也是因为自己自行脑补 搞得别人误会了一些事情

我和w🐶说了之后 w🐶因为这事儿在凌晨4点的寝室笑的吵醒室友..

嗯 至于是什么事情 还是gone with the wind吧 思沁都无语了 只能说要更稳重一点