[C++知识库]Codeforces Round #776 (Div. 3)

A. Deletions of Two Adjacent Letters

题意：
给你一个字符串，一次可以删除相连的两个字符，问最后能否只剩下一个c字符。
题解：
奇数位置是否存在c字符。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 1000005
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}

void solve(){
	string s;
	char t;
	cin>>s>>t;
	for(int i=0;i<s.length();i+=2){
		if(s[i]==t){
			cout<<"YES\n";
			return ;
		}
	}
	cout<<"NO\n";
	return ;
}
int main() 
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
    return 0;
}

B. DIV + MOD

题意：
问[l,r]区间内，$\frac{x}{a}+x\%a$的最大值。
题解：
在一个$[k?a,k?a+a)区间内，k?a+a?1的函数值最大$

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 1000005
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}

void solve(){
	int l,r,a;
	cin>>l>>r>>a;
	int kl=l/a,kr=r/a;
	if(kl==kr)cout<<r/a+r%a<<"\n";
	else{
		int ans=(kr-1)+a-1;
		ans=max(ans,r/a+r%a);
		cout<<ans<<"\n";
	}
	return ;
}
int main() 
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
    return 0;
}

C. Weight of the System of Nested Segments

题意：
有m个点，每个点有一个贡献值$a_i$要求选2*n个点使得n个区间为包含关系，求2n个点的贡献最小。
题解：
选2n个贡献最小的点，按位置排个序，每次选最左的和最右的。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 200005
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}
struct node{
	int x,w,id;
	bool operator<(const node&a){
		return w<a.w;
	}
}po[maxn];
void solve(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>po[i].x>>po[i].w,po[i].id=i;
	sort(po+1,po+1+m);
	vector<pair<int,int> >ans;
	ll sum=0;
	for(int i=1;i<=2*n;i++)ans.push_back(make_pair(po[i].x,po[i].id)),sum+=po[i].w;
	cout<<sum<<"\n";
	sort(ans.begin(),ans.end());
	for(int i=1;i<=n;i++){
		cout<<ans[i-1].second<<" "<<ans[2*n-i].second<<"\n";
	}
	return ;
}
int main() 
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
    return 0;
}

D. Twist the Permutation

题意：
有一个数组(1,2,…n)，每次$i$操作为前i个数循环右移一位。问怎么操作最少的次数才能使得数组等于a数组。
题解：
前$n?1$的操作都不影响$n$的位置，$n$的位置偏移量就是$n$操作的次数，然后更新前$n?1$个数的位置，一直递推下去。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 200005
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}
int a[2222],b[2222],pos[2222],ans[2222];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
	int now=0;
	for(int i=n;i>=1;i--){
		b[i]=(pos[i]-i+i)%i;
		ans[i]=(b[i]%i+i)%i;
		for(int j=1;j<=i-1;j++)pos[j]=(pos[j]-ans[i]+i)%i;
		now+=ans[i];
	} 
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
	cout<<"\n";
}
int main() 
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
    return 0;
}

E. Rescheduling the Exam

题意：
有n门考试，没门考试的休息时间为$t[i]?t[i?1]?1$，现在你能改变一门考试的时间，问最大的最小休息时间为多少。
题意：
休息时间最小的两门之一一定要移动，两门都计算下答案。可以模拟，也可以直接二分答案。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 200005
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}
ll a[maxn],b[maxn];
ll n,d;
bool check(ll x){
	ll index=0;
	for(int i=1;i<=n;i++){
		if((a[i]-a[i-1]-1)<x)
		{
			index=i;
			break;
		}
	}
	if(!index)return true;
	ll cnt=0,f=0;
	for(int i=1;i<=n;i++){
		if(i!=index)b[++cnt]=a[i];
	}
	if(d-b[cnt]-1>=x)f=1;
	for(int i=1;i<n;i++){
		if(b[i]-b[i-1]-1<x){
			f=0;
			break;
		}
		if(b[i]-b[i-1]>=x*2+2)f=1;
	}
	if(f)return true;
	index--;cnt=0;f=0;
	if(index==0)return false;
	for(int i=1;i<=n;i++){
		if(i!=index)b[++cnt]=a[i];
	}
	if(d-b[cnt]-1>=x)f=1;
	for(int i=1;i<n;i++){
		if(b[i]-b[i-1]-1<x){
			f=0;
			break;
		}
		if(b[i]-b[i-1]>=x*2+2)f=1;
	}
	if(f)return true;
	return false;
}
void solve(){
	cin>>n>>d;
	for(int i=1;i<=n;i++)cin>>a[i];
	ll l=0,r=d;
	while(l<r-10){
		ll mid=(l+r)>>1;
		if(check(mid))l=mid;
		else r=mid;
	}
	for(int i=r;i>=l;i--){
		if(check(i)){
			cout<<i<<"\n";
			return; 
		}
	}
}
int main() 
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
    return 0;
}

F. Vitaly and Advanced Useless Algorithms

题意：
有n件事情要完成，每件事情有个时间限制$t_i$,要在时间限制之内完成，你有m个操作，每个操作(e,t,p)代表你可以花费t的时间完成e的百分之p。问你怎么操作才能完成所有事情或者不可能。
题解：
对于每一件事情，完成它的最少时间都是独立的，每个操作都只对一个事件，我们可以用最小背包来计算完成这件事情的最小花费，然后按照时间限制从小到大来完成这些事件，记录一下路径即可。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 200005
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}
struct node{
	int v,w,id;
	bool operator<(const node&a){
		return v<a.v;
	}
};
struct ww{
	int t,id;
	bool operator<(const ww&a){
		return t<a.t;
	}
}t[maxn];
vector<node>v[maxn];
int dp[maxn][111];
vector<int>ans;
int DP(int x){
	for(int i=0;i<=v[x].size();i++){
		for(int j=0;j<=100;j++)
			dp[i][j]=INF;
	}
	dp[0][0]=0;
	int i=0;
	for(auto &it:v[x]){
		++i;
		int cost=it.v,val=it.w;
		for(int j=0;j<=100;j++)dp[i][j]=dp[i-1][j];
		for(int j=0;j<=100;j++){
			int k=min(100,val+j);
			dp[i][k]=min(dp[i][k],dp[i-1][j]+cost);
		}
	}
	int now=100;
	for(int i=v[x].size();i>=1;i--){
		node a=v[x][i-1];
		if(dp[i][now]==dp[i-1][now])continue;
		ans.push_back(a.id);
		for(int k=0;k<=100;k++){
			int qwq=min(100,k+a.w);
			if(qwq==now&&(dp[i-1][k]+a.v)==dp[i][now]){
				now=k;
				break;
			}
		}
	}
	return dp[(int)v[x].size()][100];
}
void solve(){
	int n,m;
	cin>>n>>m;
	ans.clear();
	for(int i=1;i<=n;i++)cin>>t[i].t,t[i].id=i;
	sort(t+1,t+1+n);
	for(int i=1;i<=n;i++)v[i].clear();
	for(int i=1,u,e,w;i<=m;i++){
		cin>>u>>e>>w;
		v[u].push_back({e,w,i});
	}
	int s=0;
	for(int i=1;i<=n;i++){
		s+=DP(t[i].id);
		if(s>t[i].t){
			cout<<"-1\n";
			return;
		}
	}
	cout<<ans.size()<<"\n";
	for(auto &v:ans){
		cout<<v<<" ";
	}
	cout<<"\n";
}
int main() 
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	} 
    return 0;
}

G. Counting Shortcuts

题意：
有一张图，问从s到t的花费等于s到t的最短路径或者最短路径+1的方案数。
题解：
首先最多路径只能对一次，所以不能走回头路，否则最少多2.那么就可以bfs算出所有的到s，t的距离和方案。
然后若ds[i]+dt[j]+1=ds[t]+1就是合法方案，方案为fs[i]*ft[j]，避免重复计算，规定ds[i]=ds[j]时计数。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
#include <iomanip>
#include <deque>
#include <time.h>
#include <bitset>
using namespace std;
#define ll long long
#define maxn 200005
#define mod 1000000007
#define MOD 998244353
#define Mod 1000000009
#define eps 1e-10
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll INF=0x3f3f3f3f;
const ll mod1=1e9+7;
const ll mod2=1e9+9;
template <typename T>
inline void read(T& X) {X = 0; int w = 0; char ch = 0;while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();if (w) X = -X;}
char F[200];inline void write(int x){if(x == 0){putchar('0');return;}int tmp = x > 0 ? x : -x;int cnt = 0;if(x < 0)putchar( '-' );while(tmp > 0){F[cnt++] = tmp % 10 + '0';tmp /= 10;}while(cnt > 0)putchar(F[--cnt]) ;}
template<typename T> void print(T x){if(x>9) print(x/10);putchar(x%10+'0');}
ll q_pow(ll x,ll y,ll M){ll ans=1;while(y){if(y%2){y--;ans=ans*x%M;}else {y/=2;x=x*x%M;}}return ans;}
vector<int>g[maxn];
ll ds[maxn],dt[maxn],fs[maxn],ft[maxn],n,m,s,t;
void bfs(){
	for(int i=1;i<=n;i++)ds[i]=-1,dt[i]=-1,fs[i]=0,ft[i]=0;
	queue<int>q;
	q.push(s);ds[s]=0;fs[s]=1;dt[t]=0;ft[t]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(auto &v:g[u]){
			if(ds[v]==-1){
				ds[v]=ds[u]+1;
				q.push(v);
			}
			if(ds[v]==ds[u]+1){
				fs[v]=(fs[v]+fs[u])%mod;
			}
		}
	}
	q.push(t);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(auto &v:g[u]){
			if(dt[v]==-1){
				dt[v]=dt[u]+1;
				q.push(v);
			}
			if(dt[v]==dt[u]+1){
				ft[v]=(ft[v]+ft[u])%mod;
			}
		}
	}
}
void solve(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=n;i++)g[i].clear();
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bfs();
	ll ans=fs[t];
	for(int i=1;i<=n;i++){
		for(auto &j:g[i]){
			if(ds[i]+dt[j]==ds[t]&&ds[i]==ds[j]){
				ans=(ans+fs[i]*ft[j]%mod)%mod;
			}
		}
	}
	cout<<ans<<"\n";
}
int main() 
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	} 
    return 0;
}