6.14训练日记

床睡得还不是很习惯,起晚了点.
12点开始训练(未吃饭),先打开cf逛一逛.

一 :C. Manipulating History(思维)

链接
题意:一开始你有一个长度为1的字符串.第i次 *** 作中,可以把 t 2 i − 1 t_{2i-1} t2i−1​替换成 t 2 i t_{2i} t2i​.然而现在给你的是一堆 t i t_i ti​,和最终得到的字符串 S S S.问你最开始的字符串是哪个?保证这个答案是唯一的.
思路:非常重要的观察,一开始只有一个字母,我们也只需要找到这个字母就可以.让我们思考一下,我们需要把长度为1最开始的字符串逐个替换得到这个最终字符串S.
s->S1->S2->…S
当S的长度为1时,又由于答案是唯一的,肯定是逐个字符替换,每个非答案的字母出现了偶数次,只有一个字母出现了奇数次.那个就是最终的答案(除了最后一个)
比如说长度为1,n=4 a b b c,c 那么答案就一定是a. a->b,b->c这样变化,然后最后的c会重复出现在n+1个
当S长度不是1的时候,情况是类似的.当某个字母中间需要替换(或者最后)时,它一定会导致偶数次的出现情况.又因为答案是唯一的,所以答案是出现次数为奇数次的字母.
代码:

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--){
		int n;cin>>n;
		map<char,int> cnt;
		for(int i=1;i<=2*n+1;i++){
			string s;cin>>s;
			for(auto x : s) cnt[x]++;
		}
		for(auto [x,y]:cnt){
			if(y%2==1){
				cout<<x<<"\n";
				break;
			}
		}
	}
}

二: D. Traps(贪心)

第二题
大意:n个陷阱,每个陷阱造成 a i a_i ai​伤害.可以跳过 k k k个陷阱,但每跳过一个陷阱,下一个陷阱伤害会加1.
问你最少受多少伤害.
思路:读了半天好像发现又读错题了,增加的伤害是递增的,比如你跳了一次,下一个伤害会加1.跳了两次下次伤害会增加2,累加的伤害不会取消掉.思路比较混乱,想了几个假算法后还是转向了题解.
题解巧妙构造证明了跳k次是必须的.
那么可以看作跳过一次陷阱造成的伤害是: n − i n-i n−i,(后面有 n − i n-i n−i个陷阱都多造成了1伤害),然而由于后面还有陷阱,在第一次陷阱多造成了k-1个，第二个多造成了k-2个…第i个多造成了0个.
令 t o t = a i − ( n − i ) tot=ai-(n-i) tot=ai−(n−i),选取前k个tot值较大的，认为他们就是选中的跳过的陷阱.
a n s = s u m − t o t = ∑ a i − a j + ( n − j ) ans=sum-tot=\sum{ai}-a_j+(n-j) ans=sum−tot=∑ai−aj​+(n−j)j为上一行 认为选中陷阱的编号,事实上已经不需要知道这些了编号j了.
代码：

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--){
		int n,k;cin>>n>>k;
		vector<int> a(n+1,0);
		ll sum=0;
		for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
		if(n==k){
			cout<<0<<"\n";
			continue ;
		}
		vector<int> b;
		for(int i=1;i<=n;i++){
			b.push_back(a[i]-(n-i));
		}
		sort(b.begin(),b.end());
		reverse(b.begin(),b.end());
		ll tot = 0;
		for(int i=0;i<k;i++) tot+=b[i];
		cout<<sum-tot-(1LL)*k*(k-1)/2<<"\n";
	}
}

`

三:NC21507(逆元水题)

链接
裸题一个,照着题目做就是了,求个逆元.
发现了一个常见的错误,求逆元的时候的快速幂,底数要先取一次模.

#include
using namespace std;
const int maxn = 2e5+5;
const int INF = 1e9+7;
typedef long long ll;
ll mod = 100000007;
typedef pair<int,int> pii;
ll inv[maxn];
ll f_pow(ll a,ll b){
	a%=mod;
	ll ans =1;
	while(b){
		if(b&1) ans =ans*a%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}
ll fac[maxn];
void get_mod(int n){
	//inv(i) = (mod -mod/i)*inv(mod%i)
	//inv(i!) = inv(i+1!)*i+1
	fac[1]=1;
	for(int i=2;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	inv[n] = f_pow(fac[n],mod-2);
	for(int i=n-1;i>=1;i--){
		inv[i] = inv[i+1]*(i+1)%mod;
	}
}
ll C(ll n,ll m){
	return fac[n]*inv[n-m]%mod*inv[m]%mod;
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;cin>>n;
	get_mod(2*n);
	ll res = 1;
	for(ll i=2;i<=n;i++){
		ll tmp = (C(2*i,i) - C(2*i,i+1) )%mod;
		tmp = (tmp+mod)%mod;
		res = (res+tmp)%mod;
	}
	cout<<res<<"\n";
}

四:NC17507

别在这里发电
需要维护区间乘的信息,然后还需要动态修改一个点的信息.考虑下用树状数组偷懒维护下.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
ll mod = 1e9+7;
int tree[maxn];int n;
ll f_pow(ll a,ll b){
	a%=mod;
	ll ans = 1;
	while(b){
		if(b&1) ans = ans*a%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}
ll inv(ll n){
	return f_pow(n,mod-2);
}
void update(int pos,int val){
	while(pos<=n){
		tree[pos]=(tree[pos]*val)%mod;
		pos +=(pos&(-pos));
	}
}
ll query(int pos){
	ll ans = 1;
	while(pos){
		ans = ans*tree[pos]%mod;
		pos -=(pos&(-pos));
	}
	return ans;
}
ll query(ll l,ll r){
	return query(r)*inv(query(l-1))%mod;
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) tree[i]=1;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		if(x==1){
			update(y,z);
		}
		else if(x==2){
			update(y,inv(z));
		}
		else {
			cout<<query(y,z)<<"\n";
		}
	}
}

五:A. The Enchanted Forest

链接
思路:当k>n的时候,显然有一个方案是在开始第一个点k-n天,剩下n天挨个走过去收集.
k<=n时,转化为求一个长度为k的区间和.开一个前缀和维护下再扫描一遍即可.
记得开long long,可能会爆.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		ll n,k;cin>>n>>k;
		ll sum = 0;
		vector<int> a(n+1,0);
		for(int i=1;i<=n;i++){
			cin>>a[i];sum+=a[i];
		}
		if(k>=n){
			cout<<sum+(k-n)*n+n*(n-1)/2<<"\n";
		}
		else{
			vector<ll> pre(n+1,0);
			for(int i=1;i<=n;i++) pre[i] = pre[i-1]+a[i];
			//找到长度为k的最大的子段和.
			ll res = 0;
			for(int i=1;i<=n-k+1;i++){
				int r  = i+k-1;
				res=max(pre[r]-pre[i-1],res);
			}
			cout<<res +k*(k-1)/2<<"\n";
		}
	}
}