欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2019-11-12

程序员文章站 2022-06-11 20:21:59
...

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

我实在是不想写了,于是我选择粘题解。
2019-11-12

注意这里为什么需要用主席树:因为在计算时我们必须保证ti>vt_i>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

一道很好的题。我们考虑每一位对答案的贡献。显然每一位对答案的贡献受在当前位后面的最近的加号的影响。我们考虑枚举最近的加号在当前为后面的情况:若当前位为ii,离其最近的加号在其后面jj位,显然贡献为:10j1((n1)jk1)10^{j-1}*\displaystyle \binom {(n-1)-j}{k-1} 然后你会惊奇的发现,所有的加号在某一位的后面jj位,它们的这个系数都是一样的。 另外对于ii位来说,加号可能在其后面[1,ni][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;
}

推荐阅读