seuOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
讨论
综合

第四届「帆软杯」东南大学大学生程序设计竞赛（冬季）- 初赛题解（非官方）

xukuan 2023-03-12 20:14:36 2023-03-16 22:38:10

题目难度排序：F<H<CD<I构造<BEG<A<I数位dp

A.构造数据

先考虑在什么情况下会出错

设j跑完一次循环后，发生变化的格子记作cic_i，满足1≤c1<c2<...<cm≤n1 \leq c_1<c_2<...<c_m \leq n，其中ci+1c_{i+1}就是第一个比cic_i小的数字。发生变化的过程是ac1−>acm,aci+1−>aci,2≤i≤ma_{c_1}->a_{c_m},a_{c_{i+1}}->a_{c_i},2 \leq i \leq m

  1. ∀i≠j,ai≠aj\forall i \neq j,a_i \neq a_j：设1≤i<j<k≤n,aj>ai>ak1 \leq i<j<k \leq n,a_j>a_i>a_k，同时i和k所在的位置的值会发生变化，而这种变化对j这个位置的逆序对没有影响——尽管一个数字被拿走，但又有一个数字补了进来，总数不变。其他情况不会有影响。
  2. ∃i≠j,ai=aj\exists i \neq j,a_i=a_j：设1≤i<j<k≤n,ai=aj>ak1 \leq i<j<k \leq n,a_i=a_j>a_k，同时i和k所在的位置的值会发生变化，此时j这个位置的逆序对个数减少了1。其他情况不会有影响。

所以当且仅当∃1≤i<j<k≤n,ai=aj>ak\exist 1 \leq i<j<k \leq n,a_i=a_j>a_k时会出现错误

再考虑如何统计正确答案的个数

当ai=aj,1≤i<j≤na_i=a_j,1 \leq i<j \leq n时，∀j<k≤n,aj≤ak\forall j<k \leq n,a_j \leq a_k时，答案不会出错

我们考虑对于一个满足条件的序列，加入k个值大于原序列最大值的数的总方案数。

显然第一个数可以随便放，剩下的k-1个必须都放在最后，总共有size+1种方案

最后再考虑何时会impossible

当且仅当数列中最小的数之外的数都只出现一次时，任意排列都符合条件

代码是在学校的机房里写的，没有Dev_C++，只有Visual Code，所以显的很乱

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N = 100010,mod = 19260817;
ll n, m, a[N], b[N],c[N],ans,sum;

inline ll read() {
	ll x = 0, tmp = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') tmp = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return tmp * x;
}

int main() {
	n = read();
	for (ll i = 1; i <= n; i++) b[i] = a[i] = read();
	sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n);
	m = unique(b + 1, b + 1 + n) - b - 1;
	for (ll i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + m, a[i]) - b;
	for (ll i = 1; i <= n; i++) c[a[i]]++;
	ans = 1;
	bool flag=0;
	for (ll i = 1; i <= m; i++) {
		ans = ans * (sum+1)%mod;
		sum += c[i];
		if(i>1&&c[i]>=2) flag=1;
	}
	if(flag) cout << (ans + 1) % mod << endl;
	else cout << "Impossible!\n";
	return 0;
}

B.简单平衡树

这题的数据范围不大对劲

1≤m≤3∗107,1≤vmax≤5∗105,95≤per≤1001 \leq m \leq 3*10^7,1 \leq vmax \leq 5*10^5,95 \leq per \leq 100

所以这题要把时间复杂度不能出现log2mlog_2m,要把log转移到vmax上，因此不能直接拖treap的板子

单点修改，区间查询，考虑树状数组

因为34两种操作最多只占5%，所以一次查询O(log22vmax)O(log_2^2vmax)的时间复杂度可以接受

但是树状数组不包括0，所以最后处理的时候要+1或-1，具体看代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define uint unsigned int
using namespace std;

uint seed;
uint rnd(uint &seed){
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return seed;
}
const int M=500010;
int m,vmax,per,tr[M],f[M];

inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	int y=10,len=1;
	while(y<=x){
		y=(y<<3)+(y<<1);
		len++;
	}
	while(len--){
		y/=10;
		putchar(x/y+48);
		x%=y;
	}
}

inline int lowbit(int x){
	return x&(-x);
}

inline void update(int x,int val){
	for(int i=x; i<=vmax; i+=lowbit(i)) tr[i]+=val;
}

inline int query(int x){
	int ans=1;
	for(int i=x; i; i-=lowbit(i)) ans+=tr[i];
	return ans;
}

int main(){
	int sum=1; f[0]=1;
	cin>>m>>seed>>vmax>>per;
	for(int i=1; i<=m; i++){
		int op=rnd(seed)%100+1;
		if(op<=per){
			int x=rnd(seed)%vmax+1;
			if(op%2==0){
//				cout<<"1:"<<x<<endl;
				update(x,1);
				sum++; f[x]++;
			}
			else{
//				cout<<"2:"<<x<<endl;
				if(f[x]){
					update(x,-1);
					sum--; f[x]--;
				}
			}	
		}
		else{
			if(op%2==0){
				int x=rnd(seed)%sum+1;
//				cout<<"3:"<<x<<endl;
				int l=0,r=vmax,ans=-1;
				while(l<=r){
					int mid=(l+r)>>1;
					if(query(mid)>=x){
						ans=mid;
						r=mid-1;
					}
					else l=mid+1;
				}
				write(ans); putchar('\n');
			}
			else{
				int x=rnd(seed)%vmax+1;
//				cout<<"4:"<<x<<endl;
				if(f[x]){
					write(query(x-1)+1);
					putchar('\n');
				}
				else{
					putchar('-'); putchar('1');
					putchar('\n');
				}
			}
		}
	}
	return 0;
}

C.小Q的棋子

吹起过后仍然存在的棋子的原始位置肯定是一个矩阵

换一种考虑方式：棋子不动，棋盘动

用nowid记录棋盘左上角的位置，x1,y1,x2,y2{x1,y1,x2,y2}记录存在的棋子的四条边

注意最后乘法的时候要分开取max，如果合在一起可能会负负得正

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

ll n,m,q,x1,Y1,x2,y2;
struct{
	ll x,y;
}nowid;

inline ll read(){
    ll x=0,tmp=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') tmp=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }
    return tmp*x;
}

inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    ll y=10,len=1;
    while(y<=x){
        y=(y<<3)+(y<<1);
        len++;
    }
    while(len--){
        y/=10;
        putchar(x/y+48);
        x%=y;
    }
}

int main(){
	n=read(); m=read(); q=read();
	x1=1; Y1=1; x2=n; y2=m;
	nowid.x=nowid.y=1;
	while(q--){
		ll op=read();
		switch(op){
			case 0:{
				nowid.x++;
				x1=max(x1,nowid.x);
				break;
			}
			case 1:{
				nowid.y--;
				y2=min(y2,nowid.y+m-1);
				break;
			}
			case 2:{
				nowid.x--;
				x2=min(x2,nowid.x+n-1);
				break;
			}
			case 3:{
				nowid.y++;
				Y1=max(Y1,nowid.y);
				break;
			}
		}
		write(max(0ll,y2-Y1+1)*max(0ll,x2-x1+1)); putchar('\n');
	}
	return 0;
}

D.炉石传说

题意是求3y≤n−5x3y \leq n-5x的自然数解的个数

答案是∑x=0[n5]n−5x+1\sum_{x=0}^{[\frac{n}{5}]}n-5x+1

但不能暴力循环求

而且n减15，答案数多n-3，用等差数列算

n<15n<15的时候就直接暴力求吧

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

ll T,n,ans;

inline ll read(){
	ll x=0,tmp=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') tmp=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return tmp*x;
}

int main(){
	T=read();
	while(T--){
		n=read(); ans=0; ll mod=n%15+15;
		if(n==0){
			cout<<1<<endl;
			continue;
		}
		ans=(mod-3+n-3)*((n-mod)/15+1)/2;
		//for(; n>=15; n-=15) ans+=n-3;
		for(n=mod-15; n>=0; n-=5) ans+=n/3+1;
		cout<<ans<<endl;
	}
	return 0;
}

E.铺地毯

HW≤140HW \leq 140推出min(H,W)≤12min(H,W) \leq 12

这个数据范围明显是状压

令fi,j,kf_{i,j,k}表示前i-1行填满，第i行状态为j，总共用了k个1*2个方格的状态，j的某位为1代表这个格子被填了

初始状态就用线性dp来推

首先这一行没填的，下一行都要用竖着的1*2的方格来填，用Next记录下一行必须这样的格子的状态，l记录下一行的状态

对于下一行剩下的方格，假设要用s个横着的1*2的方格来填，总共有f1,l xor Next,sf_{1,l \space xor \space Next,s}种方案

注意卡常

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll mod=1000000007;
ll h,w,a,b,f[150][1<<12][80];

inline ll lowbit(ll x){
	return x&(-x);
}

inline ll allbit(ll x){
	ll ans=0;
	for(; x; x-=lowbit(x)) ans++;
	return ans;
}

inline ll alltwo(ll x){
	ll ans=0;
	while(x){
		if(x%4==3){
			x>>=2;
			ans++;
		}
		else x>>=1;
	}
	return ans;
}

inline ll calc(ll x,ll s){
	ll f[13][80]={0};
	f[0][0]=1;
	f[1][0]=1;
	if((x&1)&&(x&2)) f[1][1]=1;
	for(ll i=2; i<w; i++){
		f[i][0]=1;
		for(ll j=1; j<=s; j++){
			f[i][j]=f[i-1][j];
			if((x&(1<<i))&&(x&(1<<i-1))) f[i][j]=(f[i][j]+f[i-2][j-1])%mod;	
		}
	}
	return f[w-1][s]%mod;
}

int main(){
	cin>>h>>w>>a>>b;
	if(h<w) swap(h,w);
	for(ll i=0; i<(1<<w); i++){
		ll t=alltwo(i);
		for(ll j=0; j<=t&&j<=a; j++) f[1][i][j]=calc(i,j);
	}
	for(ll i=1; i<h; i++){
		for(ll j=0; j<(1<<w); j++){
			for(ll k=0; k<=a; k++){
				if(f[i][j][k]==0) continue;
				ll Next=(1<<w)-1^j,sum=allbit(Next);
				for(ll l=Next; l<(1<<w); l=(l+1)|Next){
					ll v=alltwo(l^Next);
					for(ll s=0; s<=v&&k+sum+s<=a; s++) f[i+1][l][k+sum+s]=(f[i+1][l][k+sum+s]+f[i][j][k]*f[1][l^Next][s]%mod)%mod;
				}
			}
		}
	}
	cout<<f[h][(1<<w)-1][a]%mod<<endl;
	return 0;
}

F.循环字符串

把S变成S+S就可以不考虑环了，直接暴力比就可以

如果字符串长度加到10710^7就直接kmp

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n;

inline string copy(string s,ll l,ll r){
	string ans="";
	for(ll i=l; i<=r; i++) ans+=s[i];
	return ans;
}

inline void check(string s1,string s2){
	for(ll i=0; i<s1.size()/2; i++){
		if(copy(s1,i,i+s1.size()/2-1)==s2){
			cout<<"YES\n";
			return;
		}
	}	
	cout<<"NO\n";
}

int main(){
	cin>>n;
	while(n--){
		string s1,s2; cin>>s1; cin>>s2;
		if(s1.size()!=s2.size()){
			cout<<"NO\n";
			continue;
		}
		s1=s1+s1;
		check(s1,s2);
	}
	return 0;
}

G.太优雅了

如果一条边被选中，产生的收益就是[w+12]∗[\frac{w+1}{2}]*路径经过这条边的点对的个数，后者可以跑树上前缀和

假设最后取边权的是路径(x,y)，拆分成(x,rt)和(y,rt)两条，其中rt是x和y的LCA

那么我们对于每个点，记录它到它的子节点中，以[w+12][\frac{w+1}{2}]为边权的最长路径和次长路径（不与最长路径重合）

直接跑树上dp即可

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=200010;
ll ver[N<<1],edge[N<<1],Next[N<<1],head[N],tot;
ll n,m,dep[N],dis[N],p[N][21];
ll val[N],f[N],sum,ans;

inline ll read(){
	ll x=0,tmp=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') tmp=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return tmp*x;
}

inline void addEdge(ll x,ll y,ll z){
	ver[++tot]=y;
	edge[tot]=z;
	Next[tot]=head[x];
	head[x]=tot;
}

void dfs(ll x,ll before){
	dep[x]=dep[before]+1; p[x][0]=before;
	for(ll i=1; i<=20; i++) p[x][i]=p[p[x][i-1]][i-1];
	for(ll i=head[x]; i; i=Next[i]){
		ll y=ver[i],z=edge[i];
		if(y==before) continue;
		dis[y]=dis[x]+z;
		dfs(y,x);
	}
}

inline ll LCA(ll x,ll y){
	if(dep[x]>dep[y]) swap(x,y);
	for(ll i=20; i>=0; i--){
		if(dep[x]<=dep[y]-(1<<i)) y=p[y][i];
	}
	if(x!=y){
		for(ll i=20; i>=0; i--){
			if(p[x][i]!=p[y][i]){
				x=p[x][i];
				y=p[y][i];
			}
		}
		return p[x][0];
	}
	return x;
}

inline ll cmp(ll x,ll y){
	return x>y;
}

void calc(ll x){
	vector<ll> E; E.clear();
	for(ll i=head[x]; i; i=Next[i]){
		ll y=ver[i],z=edge[i];
		if(y==p[x][0]) continue;
		calc(y);
		val[x]+=val[y];
		E.push_back(f[y]+val[y]*((z+1)/2));
		f[x]=max(f[x],f[y]+val[y]*((z+1)/2));
	}
	sort(E.begin(),E.end(),cmp);
	if(E.size()>=2) ans=max(ans,E[0]+E[1]);
	else if(E.size()>=1) ans=max(ans,E[0]);
}

int main(){
	n=read(); m=read();
	for(ll i=1; i<n; i++){
		ll x=read(),y=read(),z=read();
		addEdge(x,y,z);
		addEdge(y,x,z);
	}
	dfs(1,0);
	while(m--){
		ll x=read(),y=read(),rt=LCA(x,y);
		val[x]++; val[y]++; val[rt]--; val[rt]--;
		sum+=dis[x]+dis[y]-2*dis[rt];
	}
	calc(1);
	cout<<sum-ans<<endl;
	return 0;
}

H.精灵的问题

记录到一个点，经过一定次数的树洞的最短路

跑dijkstra就行

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
#define prll pair<ll,ll>
using namespace std;

const ll N=205*205,M=N*4,K=1010,INF=1ll<<60;
ll ver[M<<1],edge[M<<1],Next[M<<1],head[N],tot;
ll n,m,k,ans,d[2][N],v[N];
struct{
	ll x1,y1,x2,y2;
}hole[K];
priority_queue<prll,vector<prll>,greater<prll> > q;

inline ll read(){
	ll x=0,tmp=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') tmp=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return tmp*x;
}

inline ll addEdge(ll x,ll y,ll z){
	ver[++tot]=y;
	edge[tot]=z;
	Next[tot]=head[x];
	head[x]=tot;
}

inline ll id(ll x,ll y){
	return (x-1)*n+y;
}

inline ll ksm(ll x,ll y){
	ll ans=1;
	while(y--) ans*=x;
	return ans;
}

inline void dijkstra(ll level){
	memset(v,0,sizeof(v)); v[id(n,n)]=1;
	while(!q.empty()){
		ll x=q.top().second; q.pop();
		if(v[x]) continue;
		v[x]=1;
		for(ll i=head[x]; i; i=Next[i]){
			ll y=ver[i],z=edge[i];
			if(d[level&1][y]>d[level&1][x]+z){
				d[level&1][y]=d[level&1][x]+z;
				q.push(make_pair(d[level&1][y],y));
			}
		}
	}
	ans=min(ans,d[level&1][id(n,n)]);
}

int main(){
	n=read(); m=read(); k=read();
	for(ll i=1; i<=n; i++){
		for(ll j=1; j<=n; j++){
			ll x=read();
			if(i>1) addEdge(id(i-1,j),id(i,j),x);
			if(j>1) addEdge(id(i,j-1),id(i,j),x);
			if(i<n) addEdge(id(i+1,j),id(i,j),x);
			if(j<n) addEdge(id(i,j+1),id(i,j),x);
		}
	}
	for(ll i=1; i<=m; i++){
		hole[i].x1=read();
		hole[i].y1=read();
		hole[i].x2=read();
		hole[i].y2=read();
	}
	
	memset(d[0],0x3f,sizeof(d[0])); ans=INF;
	d[0][id(1,1)]=0; q.push(make_pair(0,id(1,1)));
	dijkstra(0);
	for(ll i=1; i<=m; i++){
		memset(d[i&1],0x3f,sizeof(d[i&1]));
		if(ksm(k,i)>ans) break;
		for(ll j=1; j<=m; j++){
			if(d[(i&1)^1][id(hole[j].x1,hole[j].y1)]+ksm(k,i)>ans) continue;
			d[i&1][id(hole[j].x2,hole[j].y2)]=d[(i&1)^1][id(hole[j].x1,hole[j].y1)]+ksm(k,i);
			q.push(make_pair(d[i&1][id(hole[j].x2,hole[j].y2)],id(hole[j].x2,hole[j].y2)));
		}
		dijkstra(i);
	}
	cout<<ans<<endl;
	return 0;
}

I.优雅的数

这题有两种解法：dfs构造和数位dp

1.构造

符合条件的解很少，可以直接dfs出来，最后排序二分

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll MAXN=1000000000000000000;
const ll base[9]={1,22,333,4444,55555,666666,7777777,88888888,999999999};
ll T;
vector<ll> val;

inline ll ksm(ll x,ll y){
	ll ans=1;
	for(ll i=1; i<=y; i++) ans*=x;
	return ans;
}

void pre(ll s,ll before){
	for(ll i=0; i<9; i++){
		if(i==before) continue;
		if(s<=(MAXN-base[i])/ksm(10,i+1)){
			ll t=s*ksm(10,i+1)+base[i];
			val.push_back(t);
			pre(t,i);
		}
	}
}

int main(){
	pre(0,-1); sort(val.begin(),val.end());
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--){
		ll l,r; cin>>l>>r;
		ll L=lower_bound(val.begin(),val.end(),l)-val.begin()-1,
		   R=upper_bound(val.begin(),val.end(),r)-val.begin()-1;
		printf("%lld\n",R-L);
	}
	return 0;
}

2.数位dp

用fid,before,flagf_{id,before,flag}表示

  • 还有id位没确定
  • 上一个数字填了before
  • 已经填的位数是否和上限完全相同——现在随意填是否可能比l或r要大

的总方案数

对于位数比l和r小的解直接预处理

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

ll T,a[20],f[20][10][2],dp[20][10];

inline ll check(ll now,ll x){
	for(ll i=now; i>=now-x+1; i--){
		if(a[i]>x) return 0;
		if(a[i]<x) return 2;
	}
	return 1;
}

ll dfs(ll id,ll before,ll flag){
	if(id==0) return 1;
	if(f[id][before][flag]!=-1) return f[id][before][flag];
	ll ans=0;
	for(int i=1; i<=9&&i<=id; i++){
		if(i==before) continue;
		ll t=check(id,i);
		if(flag==0||t<=1) ans+=dfs(id-i,i,flag&&t);
		if(flag==1&&t==2) break;
	}
	return f[id][before][flag]=ans;
}

ll query(ll x){
	if(x==0) return 0;
	ll len=0;
	while(x){
		a[++len]=x%10;
		x/=10;
	}
	memset(f,-1,sizeof(f));
	ll ans=0;
	for(ll i=1; i<len; i++){
		for(ll j=1; j<=9&&j<=i; j++) ans+=dp[i][j];
	}
	return dfs(len,0,1)+ans;
}

inline void pre(){
	dp[0][0]=1;
	for(ll i=1; i<=18; i++){
		for(ll j=1; j<=9&&j<=i; j++){
			for(ll k=0; k<=9&&k<=i-j; k++){
				if(j==k) continue;
				dp[i][j]+=dp[i-j][k];
			}
		}
	}
}

int main(){
	pre();
	scanf("%lld",&T);
	while(T--){
		ll l,r; scanf("%lld %lld",&l,&r);
		printf("%lld\n",query(r)-query(l-1));
	}
	return 0;
}

共 2 条回复

dd
2023-03-16 0:05:03

B其实题目有点错误

xukuan
2023-03-16 15:51:28

当时是感觉有点奇怪，但具体错哪里也看不出来

seuOJ Powered by SYZOJ.