2019-11-12

T1

一道知道了结论就很简单的题。。 显然~~（？）~~ ,按照字典序输出的字符串满足条件。。然后用stl自带的sort排一下序就可以了。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1e6+10;
string a[maxn];
int n,tong[maxn],qaq[maxn],tot,shawn[maxn];
struct node{
	int x,y;
}ans[maxn];
inline bool cmpl(int x,int y){
	return a[x]<a[y];
}
int main(){
	freopen("block.in","r",stdin);
	freopen("block.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		cin>>a[i],qaq[i]=i;
	sort(qaq+1,qaq+1+n,cmpl);
	for(int i=1;i<=n;i++)  tong[i]=i,shawn[i]=i;
	for(int i=1,cxk,qbl;i<=n;i++){
		if(qaq[i]!=shawn[i]){
			ans[++tot]=(node){i,tong[qaq[i]]};
			cxk=shawn[i];qbl=qaq[i];
			swap(shawn[i],shawn[tong[qaq[i]]]);
			swap(tong[cxk],tong[qbl]);
		}
	}
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++)
		printf("%d %d\n",ans[i].x,ans[i].y);
	return 0;
}

T2

我实在是不想写了，于是我选择粘题解。

注意这里为什么需要用主席树：因为在计算时我们必须保证$t_i>v$ti​>v 因此可以用主席树来维护。。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long 
using namespace std;
const int maxn=2e5+10;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,x,a[maxn],ned[maxn],sufned[maxn],root[maxn],tot;
struct node{
	int ls,rs;
	long long sum;
}tree[maxn<<5];
void update(int node){
	tree[node].sum=tree[tree[node].ls].sum+tree[tree[node].rs].sum;
}
int add(int pre,int l,int r,int ql,int qr){
	int node=++tot;
	tree[node]=tree[pre];
	if(l==r){
		tree[node].sum+=qr;
		return node;
	}
	int mid=l+r>>1;
	if(ql<=mid) tree[node].ls=add(tree[pre].ls,l,mid,ql,qr);
	else tree[node].rs=add(tree[pre].rs,mid+1,r,ql,qr);
	update(node);
	return node;
}
int query(int node,int l,int r,int ql,int qr){
	if(ql<=l && r<=qr) return tree[node].sum;
	int mid=l+r>>1,sum=0;
	if(ql<=mid) sum+=query(tree[node].ls,l,mid,ql,qr);
	if(mid<qr) sum+=query(tree[node].rs,mid+1,r,ql,qr);
	return sum;
}
int check(int mid){
	int sum=0;
	int pos=lower_bound(a+1,a+1+n,mid)-a;
	sum=sufned[pos]-(mid/x)*(n-pos+1);
	if(mid%x+1<=x-1)
		sum+=query(root[pos],0,x-1,mid%x+1,x-1);
	return sum;
}
int work(int qaq){
	int l=0,r=a[n],mid,ans;
	while(l<r){
		mid=(l+r)>>1;
		if(check(mid)>qaq) l=ans=mid+1;
		else r=ans=mid;
	}
	return max(ans-qaq,(long long)0);
}
signed main(){
	n=read();m=read();x=read();
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++) ned[i]=a[i]/x;
	for(int i=n;i>=1;i--){
		sufned[i]=sufned[i+1]+ned[i];
		root[i]=add(root[i+1],0,x-1,a[i]%x,1);
	}
	for(int i=1,qaq;i<=m;i++){
		qaq=read();
		printf("%lld\n",work(qaq));
	}
}

T3

一道很好的题。我们考虑每一位对答案的贡献。显然每一位对答案的贡献受在当前位后面的最近的加号的影响。我们考虑枚举最近的加号在当前为后面的情况：若当前位为$i$i，离其最近的加号在其后面$j$j位，显然贡献为：$10^{j-1}*\displaystyle \binom {(n-1)-j}{k-1}$10j−1∗(k−1(n−1)−j​) 然后你会惊奇的发现，所有的加号在某一位的后面$j$j位，它们的这个系数都是一样的。 另外对于$i$i位来说，加号可能在其后面$[1,n-i]$[1,n−i]位，因此可以将这个系数后缀和一下。可是我们只讨论了后面有加号的情况，没有加号的情况怎么办呢？手推一下加在系数里面就好了QAQ。然后就没有然后了，注意处理阶乘和逆元。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long 
using namespace std;
const int maxn=5e5;
const int mod=998244353;
int inv[maxn+10],fac[maxn+10];
int n,k,num[maxn+10],f[maxn+10],ans;
char a[maxn+10];
int ksm(int x,int y){
	int sum=1;
	while(y){
		if(y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
void prepare_work(){
	fac[0]=1;for(int i=1;i<=maxn;i++) fac[i]=fac[i-1]*i%mod;
	inv[maxn]=ksm(fac[maxn],mod-2);
	for(int i=maxn-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int x,int y){
	if(x<0 || x<y) return 0;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
	scanf("%lld %lld",&n,&k);
	cin>>a+1;
	for(int i=1;i<=n;i++)
		num[i]=a[i]-'0';
	prepare_work();
	for(int i=n-1;i;i--){
		f[i]=(f[i+1]+ksm(10,n-i-1)*C(i-1,k-1)%mod)%mod;
	}
	for(int i=1;i<=n;i++){
		f[i]=(f[i]+ksm(10,n-i)*C(i-1,k)%mod)%mod;
	}
	for(int i=1;i<=n;i++){
		ans=(ans+f[i]*num[i]%mod)%mod;
	}
	printf("%lld",ans);
	return 0;
}