模拟赛题解以后就发在这里了

2023.10.5

CSP模拟49

ltx这场太恶心了，生理上的那种，看见要模一个大质数我就知道这题要完，这种题连暴力都tmd没法打，随便糊点分出来算了

T1 模板题

额……过

T2 THUSC

排序，两个分值，分值确定，但是分值的权值不定，让求求在不同权值下有多少种排名

我￥%&…………#%￥……&（）&……（）……￥

咱就不能好好排名吗，你把权值给了也行啊

（~~胡思乱想开始~~）

首先我们来考虑权值的变动是怎么具体影响排名的，举个例子

现在A两项分值是1 50，B两项分值是5 1

然后我给第一项一个13的权值，再给第二项一个1的权值

那A现在是13 50，B是65 1

这个13是咋得出来的，是你（50-1）/（5-1）得出来的

也就是说，出现影响的权值比为 $abs(x_1-x_2)/abs(y_1-y_2)$

那这个就可以提供一个暴力的思路,因为前几个数据点$x$和$y$的值最大也就是个$100$,也就是说这个权值比只有$1e4$种情况,我们直接暴力枚举权值比,算出不同的结果再去重,可以捞一点点分

去重操作直接hash得了

2023.10.6

NOIP A层联测6(赛时版本)

T1 万花筒

人话题意：给出一个无向带权图$G$，对于第$i$个$G$来说，根据边$(u,v,w)$转化为$((u+i)mod\ n+1,(v+i)mod\ n+1,w)$的规则,得到一个新的图,求这个图的最小生成树的权值和

数据范围:多测数据$T<=100$,$n,w<=10^9$,$m$之和$<=10^5$

最多$1e5$条边,应该算法上就是$O(nlogn)$

先手模一遍小样例

额,这个边是越来越多的

随便糊一个暴力上去,根据规则推出新边,并存入队列,将边用map记录,重边我们就不向下推,这样建图后直接跑最小生成树

(~~就是清空挺费时间的~~)

T2 冒泡排序趟数期望

打表得出来一个规律

然后呢

然后……就没了

T3 数点

k=1暴力分应该挺好写的

（~~T2打表没时间写了~~）

NOIP A层联测6（赛后版本）

T1 万花筒

一个类似于贪心的思想，首先我们按照 $d=abs(u-v)$ 对所有边分类,然后我们按照边权从小到大排序,根据题意我们可以知道,最终 $i,i+d,i+2*d...$ 这些边会连接在一起,而不在这个范围内的边有 $gcd(n,d)$ 个, $ans+=(n-gcd(n,d))*w$ ,然后就将 $n$ 更新为 $n-gcd(n,d)$ ,当 $n==1$ 停止,这时就得到了最小生成树

爱看不看,不看滚

#include<bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int x,int y){
	if(y) return gcd(y,x%y);
	else return x;
}
struct edge{
	int arr,w;
	bool operator <(const edge &x)const{
		return w<x.w;
	}
};
vector<edge> line;
int t,n,m;
int ans=0;
signed main(){
    freopen("kaleidoscope.in","r",stdin);
    freopen("kaleidoscope.out","w",stdout);
    cin>>t;
    while(t--){
        line.clear();
        ans=0;
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            int turn=abs(u-v);
            line.push_back(edge{turn,w});
        }
        sort(line.begin(),line.end());
        int now=n;
        for(edge i:line){
            int x=gcd(i.arr,now);
            if(x==now)
            continue;
            ans+=(now-x)*i.w;
            now=x;
            if(x==1)
            break;
        }
        cout<<ans<<endl;
    } 
}

T2 冒泡排序趟数期望

对于冒泡排序来说,每一趟都会让所在位置大于正确位置的数左移一位

那我们就知道了,对于一个 $n$ 个数的随机序列,它的移动趟数就应该是 $max(site[i]-i)$,$site[i]$ 是 $i$ 在此序列的初始位置

So,我们设该序列的移动趟数为$k$,

2023.10.7

CSP模拟50（赛时版本）

T1 异或

没啥好说的结论题，规律打表就能看出来

直接贴代码了

爱看不看,不看滚

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool flag=true;
int now=0,ans=0,tot=0,m,n;
void solve(){
    now++;
    if(n%2!=0){
        if(flag){
            n=n/2+1;
            tot+=n;
            ans+=now*n;
            flag=false;
        }
        else{
            n=n/2;
            tot+=n;
            ans+=now*n;
            flag=true;
        }
    }
    else{
        n=n/2;
        tot+=n;
        ans+=now*n;
    }
    if(m==tot)
    return;
    solve();
}
signed main(){
    cin>>n;
    m=n;
    solve();
    cout<<ans;
    return 0;	
}

T2 赌神

题没读明白，你筹码呢？

不是你筹码呢，你初始筹码不给我用啥啊

你总不能筹码数随意取吧，那你都有无限的筹码了，你还赌个屁啊（大雾

样例解释:

假设颜⾊为红⾊和蓝⾊。⼀开始你有$1$个筹码，红球和蓝球都有$2$个。你将在两个球上都押$\frac{1}{2}$的筹
码，幕后⿊⼿会控制红球掉落，此时你获得了$2* \frac{1}{2}=1$个筹码，此时你拥有$1$个筹码，红球和蓝球
分别有$1,2$个；
接下来，你将在红球上押$\frac{1}{3}$个筹码，在蓝球上押$\frac{2}{3}$个筹码，幕后⿊⼿会控制蓝球掉落，你将获得
$2* \frac{2}{3}= \frac{4}{3}$个筹码，此时你拥有$\frac{4}{3}$个筹码，红球和蓝球分别有$1,1$个；
然后，你将在红球上押$\frac{2}{3}$个筹码，在蓝球上押$\frac{2}{3}$个筹码，幕后⿊⼿会控制蓝球掉落，你将获得$2* \frac{2}{3}= \frac{4}{3}$
个筹码，此时你拥有$\frac{4}{3}$个筹码，红球和蓝球分别有$1,0$个；
最后，你把所有筹码全部押在红球上，幕后⿊⼿控制红球掉落，你获得了$2* \frac{4}{3}= \frac{8}{3}$个筹码，此时你
拥有了$\frac{8}{3}$。
红球与蓝球全部掉落完毕，游戏结束，你最后得到了$\frac{8}{3}$$个筹码。可以证明,$\frac{8}{3}$$是你能得到的最⼤收益。

T3 路径

大致读了一下，需要求出树上任意两点距离的$k$次方,再求和

求树上任意两点距离这个很套路了,是换根dp

我们考虑用$map$将所有的距离存起来,然后直接统计个数,快速幂求答案加起来就行了

换根dp时间复杂度是$O(n)$的,map遍历$O(n)$,快速幂$O(logn)$

总时间复杂度$O(n)$级别(~~这不纯纯扯淡吗~~)

给了$3s$的时限,$1e6$的数据,$std$肯定是$O(nlogn)$级别的啊

那问题出现在哪?

换根dp

换根dp能$O(n)$解决的问题,是求整棵树任意点对距离之和,它换根以后,根到其他点的距离和是由上一个根的距离和用转移方程$O(1 )$转换出来的

但是现在我们要求的不是距离和,而是单个的所有距离,这就麻烦起来了

得,换根dp假了

不过先写一份伪代码(~~换根dp咋打我是真忘了~~)

这个dp还不如直接遍历打暴力……

爱看不看,不看滚

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10;
int n,k;
struct edge{
    int to,next;
}e[maxn<<1];
int head[maxn],cnt;
int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}
void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
map<int,int>mp;
void dfs(int x,int fa){
    siz[x]=1;
    dep[x]=dp[fa]+1;
    for(int i=head[x];i;i=e[i].next){
        int to=e[i].to;
        if(to==fa)
        continue;
        dfs(to,x);
        siz[x]+=siz[to];
    }
}
void turn_dp(int x,int fa){
    for(int i=head[x];i;i=e[i].next){
        int to=e[i].to;
        if(to==fa)
        continue;
        rand(son(x))--;//x的子树内所有点对应距离减一
        rand(other(son(x)))++;//其余点加一
        map[rand(all)]++;//将新距离存储
        turn_dp(to,x)
    }
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    turn(1,0);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=(ans+qpow(i,k)*map[i]%mod)%mod;
    }
    cout<<ans;
}

T4 树

数据范围$3e5$,给了足足$6s$的时限,树形结构,修改加查询,猜测这道题正解是树分块(~~对,我还是不会打~~)

2023.10.9

NOIP A层联测8(赛时版本)

T1 集合

浅浅打个表（~~对，我又开始打表了~~）

然后发现了一个规律，得到了一个转移方程

我们设$dp[i]$代表子集和为$i$子集数量

然后我们枚举当前子集的最大值

那么就可以得到$$dp[j]=dp[j]+dp[j-i]$$

$j$由$i$来确定,不难发现$j$的取值范围是$[i,i*(i+1)/2]$

也就是当前子集只包含$i$到包含$(1,i)$

可以发现,下标较小的$dp[]$会影响下标较大的,所以倒叙枚举,防止同一层枚举影响同一层较大下标的答案

就做出来了

要注意,因为$dp$中相当于存储的是指数,所以需要让$dp$对$mod-1$取模

爱看不看,不看滚

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int maxn=210;
int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1,a=a*a%mod){
    	if(b&1){
    		ans=ans*a%mod;
		}       
	}
    return ans;
}
int num[maxn*maxn];
int n;
signed main(){
	cin>>n;
	num[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=i*(i+1)/2;j>=i;j--){
			num[j]=(num[j]+num[j-i])%(mod-1);
		}
	}
	int ans=1;
	for(int i=1;i<=n*(n+1)/2;i++){
		//cout<<num[i]<<" ";
		ans=ans*qpow(i,num[i])%mod;
	}
	cout<<ans;
}

NOIP A层联测8(赛后版本)

T1 集合

爱看不看,不看滚

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int maxn=210;
int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1,a=a*a%mod){
    	if(b&1){
    		ans=ans*a%mod;
		}       
	}
    return ans;
}
int num[maxn*maxn];
int n;
signed main(){
	cin>>n;
	num[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=i*(i+1)/2;j>=i;j--){
			num[j]=(num[j]+num[j-i])%(mod-1);
		}
	}
	int ans=1;
	for(int i=1;i<=n*(n+1)/2;i++){
		//cout<<num[i]<<" ";
		ans=ans*qpow(i,num[i])%mod;
	}
	cout<<ans;
}

2023.10.10

CSP模拟51(赛时版本)

T1 菜

其实挺好做的,用一个栈来存入元素每次看是否可以合并,能合并就直接合,不能就直接存进栈

最后栈内元素只有1时输出"Yes"

第一班打了一个vector遍历的版本,先不说时间复杂度的问题,因为一些未知原因它炸了

爱看不看,不看滚

#include<bits/stdc++.h>
using namespace std;
bool st[710][710];
vector<int> num[710];
stack<int> s1;
stack<int> s2;
int n;
int main(){
	freopen("2.in","r",stdin);
	cin>>n;
	for(int i=2;i<=700;i++){
		for(int j=1;j<=sqrt(i);j++){
			if(i%j==0){
				if(j!=1)
				num[i].push_back(j);
				if(i!=j)
				num[i].push_back(i/j);
			}
		}
	}
	int tot=0;
	int turn;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		if(s1.empty()){
			tot++;
			s1.push(tot);
			for(auto f:num[x]){
				st[tot][f]=true;
			}
		}
		else{
			turn=s1.top();
			bool flag=false;
			for(auto f:num[x]){
				//cout<<f<<" ";
				if(st[turn][f]==true){
					for(auto g:num[x]){
						st[turn][g]=true;
					}
					flag=true;
					break;
				}
			}
			//cout<<endl;
			if(!flag){
				tot++;
				s1.push(tot);
				for(auto f:num[x]){
					st[tot][f]=true;
				}
				//cout<<i<<" "<<tot<<endl;
			}
		}
		cout<<i<<" "<<x<<endl;
	}
	
	if(s1.size()==1){
		cout<<"Yes";
		return 0;
	}
	bool tag=false;
	int last=s1.size();
	while(1){
		if(tag==false){
			turn=s1.top();
			if(s2.empty()){
				s2.push(turn);
			}
			else{
				bool flag=false;
				for(int i=2;i<=n;i++){
					if(st[s2.top()][i]&&st[turn][i]){
						for(int j=2;j<=n;j++){
							if(st[turn][i]){
								st[s2.top()][i]=true;
							}
						}
						flag=true;
						break;
					}
				}
				if(!flag){
					s2.push(turn);
				}
			}
			s1.pop();
			if(s1.empty()){
				tag=true;
				if(s2.size()==last){
					cout<<"No";
					return 0;
				}
				if(s2.size()==1){
					cout<<"Yes";
					return 0;
				}
				last=s2.size();
			}
		}
		else{
			turn=s2.top();
			if(s1.empty()){
				s1.push(turn);
			}
			else{
				bool flag=false;
				for(int i=2;i<=n;i++){
					if(st[s1.top()][i]&&st[turn][i]){
						for(int j=2;j<=n;j++){
							if(st[turn][i]){
								st[s1.top()][i]=true;
							}
						}
						flag=true;
						break;
					}
				}
				if(!flag){
					s1.push(turn);
				}
			}
			s2.pop();
			if(s2.empty()){
				tag=false;
				if(s1.size()==last){
					cout<<"No";
					return 0;
				}
				if(s1.size()==1){
					cout<<"Yes";
					return 0;
				}
				last=s1.size();
			}
		}
	}
}

所以改了一个bitset版本，空间更小，速度更快

爱看不看,不看滚

#include<bits/stdc++.h>
using namespace std;
bitset <710>bit[710];
bitset <710>st[100100]; 
bitset <710>sta[100100];
bitset <710>site;
int n;
int main(){
	//freopen("2.in","r",stdin);
	cin>>n;
	for(int i=2;i<=700;i++){
		for(int j=1;j<=sqrt(i);j++){
			if(i%j==0){
				if(j!=1)
				bit[i][j]=1;
				if(i!=j)
				bit[i][i/j]=1;
			}
		}
	}
	int top1=0,top2=0;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		if(top1==0){
			top1++;
			st[top1]=bit[x];
		}
		else{
			site=(st[top1]&bit[x]);
			if(site.any()){
				st[top1]=(st[top1]|bit[x]);
			}
			else{
				top1++;
				st[top1]=(bit[x]);
			}
		}
		//cout<<top1;
	}
	if(top1==1){
		cout<<"Yes";
		return 0;
	}
	int turn;
	bool tag=false;
	int last=top1;
	while(1){
		//cout<<top1<<" "<<top2<<endl;
		if(tag==false){
			turn=top1;
			if(top2==0){
				top2++;
				sta[top2]=st[turn];
			}
			else{
				site=(sta[top2]&st[turn]);
				if(site.any()!=0){
					sta[top2]=(sta[top2]|st[turn]);
				}
				else{
					top2++;
					sta[top2]=st[turn];
				}
			}
			top1--;
			if(!top1){
				tag=true;
				if(top2==last){
					cout<<"No";
					return 0;
				}
				if(top2==1){
					cout<<"Yes";
					return 0;
				}
				last=top2;
			}
		}
		else{
			turn=top2;
			if(top1==0){
				top1++;
				st[top1]=sta[turn];
			}
			else{
				site=(st[top1]&sta[turn]);
				if(site.any()!=0){
					st[top1]=(st[top1]|sta[turn]);
				}
				else{
					top1++;
					st[top1]=sta[turn];
				}
			}
			top2--;
			if(!top2){
				tag=false;
				if(top1==last){
					cout<<"No";
					return 0;
				}
				if(top1==1){
					cout<<"Yes";
					return 0;
				}
				last=top1;
			}
		}
	}
}

CSP模拟51(赛后版本)

T2 狗(这是真狗)

由于左右方向和上下方向互不影响，所以我们分开计算考虑

由于每一行每一列是独立的，也单独计算

so,我们对每一行和每一列单独进行dp,得到状态转移方程

设$i$表示当前狗的数量,$j$表示有多少条标记为$R$或$D$的狗还没有匹配

$f[i][j]$统计方案数,$g[i][j]$统计权值和

对于当前标记为$L$或$U$的狗,转移方程如下

\[f[i][j-1]=f[i][j-1]+f[i-1][j]*j \]

\[g[i][j-1]=g[i][j-1]+g[i-1][j]*j+f[i-1][j]*j*arr[i] \]

对于当前标记为$R$或$D$的狗,转移方程如下

\[f[i][j+1]=f[i][j+1]+f[i-1][j] \]

\[g[i][j+1]=g[i][j+1]+g[i-1][j]+f[i-1][j]*arr[i] \]

最后,将每行每列权值与除了自己这行这列所得的方案数相乘,最后相加,即为答案

模数前一定要加const!!!妈的我调了一晚上

2023.10.11

CSP模拟52(赛时版本)

T1 长春花

打了个暴力,每次暴搜查找

对,切了

爱看不看，不看滚

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
bool flag[N];
int maxn=0;
signed main(){
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	int p;
	cin>>p;
	for(int i=0;i<p;i++){
		flag[i*i%p]=true;
	}
	for(int i=0;i<p;i++){
		for(int j=0;j<p;j++){
			if(flag[(i-j*j+p)%p]){
				maxn=max(maxn,j);
				break;
			}
		}
	}
	cout<<maxn;
}

T2 紫罗兰

对于每一个点作为起点BFS，找到最小环长

当我们第一次访问$v$点时,更新其$dis$,否则得到一个$dis[u]+dis[v]+1$的环

之后就记录方案数就可以了

因为每一个点都会把这个环统计一次,所以答案要除以环长

因为奇数环两个方向都会统计,所以奇数环要再把答案除以2

爱看不看，不看滚

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int>edge[3010];
int n,m;
int minn=2e9+10;
int tot=0;
int dis[3010],len[3010];
void search(int x){
	queue<int>q;
	memset(dis,0x3f,sizeof(dis));
	memset(len,0,sizeof(len));
	q.push(x);
	dis[x]=0,len[x]=1;
	while(!q.empty()){
		int i=q.front();
		q.pop();
		for(auto j:edge[i]){
			int turnd=dis[i]+dis[j]+1;
			int turnc=len[i]*len[j];
			if(dis[j]==dis[i]||dis[j]==(dis[i]+1)){
				if(turnd<minn){
					minn=turnd;
					tot=turnc;
				}
				else if(turnd==minn){
					tot+=turnc;
				}	
			}
			if(dis[j]>dis[i]+1){
				dis[j]=dis[i]+1;
				len[j]=len[i];
				q.push(j);
			}
			else if(dis[j]==dis[i]+1){
				len[j]+=len[i];
			}
		}
	}
}
signed main(){
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		search(i);
	}
	tot/=minn;
	if(minn%2)tot/=2;
	cout<<tot;
}