Solution of Luogu September competition

程序员文章站 2022-06-10 23:43:28

...

题目传送门

显而易见地就可以发现，这个其实就是统计最多的字符的个数

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
char s[N];int a[30],Max;
int main()
{
	scanf("%s",s+1);int len=strlen(s+1);
	for(int j=1;j<=len;j++)
	  a[s[j]-'a']++;
	for(int i=0;i<27;i++)
	  Max=max(Max,a[i]);
	printf("%d",Max);
	return 0;
}

题目传送门

显而易见地可以发现，这道题只需要做3遍bfs，就可以算出两个终点和起点到任意一个点的距离， O ( n 2 ) O(n^2) O(n2)枚举两个交汇的位置，然后就可以了。（要加堆优化，还要卡常）时间复杂度： O ( n 2 l o g 2 n ) O(n^2log_2n) O(n2log2n)

#include<bits/stdc++.h>
using namespace std;
int read(){
	int num=0;bool flag=1;
	char c=getchar();
	for(;c<'0'||c>'9';c=getchar())
	  if(c=='-')flag=0;
	for(;c>='0'&&c<='9';c=getchar())
	  num=(num<<1)+(num<<3)+c-'0';
	return flag?num:-num;
}
#define ll long long
const int N=1e3+10;
int n,m,a,b,c,v[N][N];ll d[3][N][N];
struct cow{int x,y,z;};priority_queue<cow>q;
bool operator <(const cow& a,const cow&b){return a.z>b.z;}
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void bfs(int id,int stx,int sty){
    d[id][stx][sty]=v[stx][sty];
	q.push((cow){stx,sty,d[id][stx][sty]});
	while(!q.empty())
	{
		cow now=q.top();q.pop();
		if(id!=0&&now.x==1&&now.y==a)return ;
		for(int i=0;i<4;i++){
			int xx=now.x+dx[i],yy=now.y+dy[i];
			if(xx<1||xx>n||yy<1||yy>m)continue;
			if(d[id][xx][yy]>d[id][now.x][now.y]+v[xx][yy]){
				d[id][xx][yy]=d[id][now.x][now.y]+v[xx][yy]; 
				q.push((cow){xx,yy,d[id][xx][yy]});
			}
		}
	}
}
int main()
{
    memset(d,30,sizeof(d));
	n=read();m=read();a=read();
	b=read();c=read();
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    v[i][j]=read();ll Max=1000000000000000;
	bfs(0,1,a);bfs(1,n,c);bfs(2,n,b);
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    Max=min(Max,d[0][i][j]+d[1][i][j]+d[2][i][j]-2*v[i][j]);
	printf("%lld",Max);
	return 0;
}

题目传送门

当这个是一条链的情况时，就是积木大赛
其中~~非常优秀~~的O(n)做法就是通过判断前后两个的 a i 和 a i + 1 a_i和a_{i+1} ai和ai+1的大小，用sum加上 M a x ( a i + 1 − a i , 0 ) Max(a_{i+1}-a_i,0) Max(ai+1−ai,0)
那么考虑在树上如何做，那么显然，设有一个点x,他的父亲节点为 f a x fa_x fax，显然，这个x点的贡献就是 M a x ( a x − a f a x , 0 ) Max(a_x-a_{fa_x},0) Max(ax−afax,0)
那么就分开考虑，对于一个点，他可以选择的父亲的节点个数为 M i n ( i − 1 , k ) Min(i-1,k) Min(i−1,k)，设为k，那么只要枚举每个点的个数，在枚举父亲的个数，就可以求出来了
然后发现对于一个x点， f a x ∈ [ M i n ( x − k − 1 ) , x − 1 ] fa_x\in [Min(x-k-1),x-1] fax∈[Min(x−k−1),x−1]，这个具有单调的性质，那么就可以用树状数组维护，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Mod 998244353
#define lowbit(x) (x&-x)
const int N=1e6+10;
ll Sum,cnt[N],sum[N],a[N];
int n,k,tot,c[N];ll b[N];
ll getsum(ll *d,int p){
	ll sum=0;
	for(;p;p-=lowbit(p))
	  sum=(sum+d[p])%Mod;
	return sum;
}
void add(ll *d,int p,ll c){
	for(;p<=n;p+=lowbit(p))
	  d[p]=(d[p]+c+Mod)%Mod;
}
ll power(ll x,ll y){
	if(y==0)return 1;
	ll sum=power(x,y>>1);
	if(y&1)return sum*sum%Mod*x%Mod;
	  else return sum*sum%Mod;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	  scanf("%lld",&a[i]),b[i]=a[i];
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)
	  c[i]=lower_bound(b+1,b+n+1,a[i])-b;
	add(cnt,c[1],1);add(sum,c[1],a[1]);
	for(int i=2;i<=n;i++){
		if(i-k-1>0)add(cnt,c[i-k-1],-1),add(sum,c[i-k-1],-a[i-k-1]);
		ll p=power(min(i-1,k),Mod-2);ll Cnt=getsum(cnt,c[i]);
		Sum=(Sum+(Cnt*a[i]%Mod-getsum(sum,c[i])+Mod)%Mod*p%Mod)%Mod;
		add(cnt,c[i],1);add(sum,c[i],a[i]);
	}
	printf("%lld",(Sum+a[1])%Mod);
	return 0;
}

题目传送门

~~这道题我觉得部分分比正解重要~~

subtask1

用E(i)表示当前走了i步所用的期望步数
那么对于 E [ i + 1 ] = 1 2 ∗ ( 1 + E i + 1 ) ( 直接走到 i + 1 号点后又转了一圈 ) + 1 2 ∗ ( 1 + E i ) ( 直接走到 i + 1 号点 ) E[i+1]={\frac{1}{2}*(1+E_{i+1})(直接走到i+1号点后又转了一圈)}+{\frac{1}{2}*(1+E_i)(直接走到i+1号点)} E[i+1]=21∗(1+Ei+1)(直接走到i+1号点后又转了一圈)+21∗(1+Ei)(直接走到i+1号点)
显然 E 1 = 0 , 将上面的公式移项得到 E i + 1 = E i + 2 E_1=0,将上面的公式移项得到E_{i+1}=E_i+2 E1=0,将上面的公式移项得到Ei+1=Ei+2，最后求 E n E_n En，显然答案为 2 ∗ n 2*n 2∗n

subtask2

E(i)表示从i第一次到i+1的期望步数
那么显然对于答案即为 Σ i = 1 n E i \Sigma_{i=1}^{n}E_i Σi=1nEi
对于 E i = { 1 2 ∗ 1 ( 直接到达 ) 1 2 ∗ ( 1 + E i − 1 + E i ) ( 先从 i 号点到 i − 1 号点，再到 i 号点，再到 i + 1 号点 ) E_{i}=\begin{cases}\frac{1}{2}*1(直接到达)\\\frac{1}{2}*(1+E_{i-1}+E_i)(先从i号点到i-1号点，再到i号点，再到i+1号点)\end{cases} Ei={21∗1(直接到达)21∗(1+Ei−1+Ei)(先从i号点到i−1号点，再到i号点，再到i+1号点)
移项可得 E i = 2 + E i − 1 , 显然 E 1 = 2 ( 因为本身有自环，那么到 i 的概率为 1 2 , 那么期望就是 2 ) {移项可得E_i=2+E_{i-1}},显然{E_1=2(因为本身有自环，那么到i的概率为\frac{1}{2},那么期望就是2)} 移项可得Ei=2+Ei−1,显然E1=2(因为本身有自环，那么到i的概率为21,那么期望就是2)
最后显然就可以得到 Σ i = 1 n E i = 2 ∗ ( 1 + 2 + 3 + 4 + . . . + n ) = n ∗ ( n + 1 ) {\Sigma_{i=1}^{n}E_i=2*(1+2+3+4+...+n)=n*(n+1)} Σi=1nEi=2∗(1+2+3+4+...+n)=n∗(n+1)

subtask3

这个图转换一下，就可以变成一个平常的一个问题：给你一个硬币，问你抛了几次，这个硬币才会连续n次朝上，转换为上图，就是n+1次朝上（因为有要跳到n+1格上）
E(i)表示i到i+1的期望步数
那么 E i = { 1 2 ∗ 1 ( 直接往 i + 1 走 ) 1 2 ∗ ( 1 + Σ j = 1 i E j ) ( 回到了原点，然后又从 1 号点一步一步走 ) E_i=\begin{cases}\frac{1}{2}*1(直接往i+1走)\\ \frac{1}{2}*(1+\Sigma_{j=1}^{i}E_j)(回到了原点，然后又从1号点一步一步走)\end{cases} Ei={21∗1(直接往i+1走)21∗(1+Σj=1iEj)(回到了原点，然后又从1号点一步一步走)
通过找移项得到 E i = Σ j = 1 i − 1 E j + 2 E_i=\Sigma_{j=1}^{i-1}E_j+2 Ei=Σj=1i−1Ej+2
再通过找规律可以得到答案为 2 n + 1 + 2 2^{n+1}+2 2n+1+2

正解

通过上面的3个期望就可以很容易的推出下面的方程组

cnt表示有cnt条返祖边（可以是自环），E(i)表示i到i+1的期望步数
E i = { 1 c n t + 1 ∗ 1 ( 直接到达 i + 1 号点 ) 1 c n t + 1 ∗ Σ j ∈ ( 1 , i ) i 与 j 有返祖边 ( E i + Σ k = 1 j E k ) E_i=\begin{cases}\frac{1}{cnt+1}*1(直接到达i+1号点)\\\frac{1}{cnt+1}*\Sigma^{i与j有返祖边}_{j\in (1,i)}(E_i+\Sigma_{k=1}^{j}E_k ) \end{cases} Ei={cnt+11∗1(直接到达i+1号点)cnt+11∗Σj∈(1,i)i与j有返祖边(Ei+Σk=1jEk)
将其移项得 E i = 1 + Σ j ∈ ( 1 , i ) i 与 j 有返祖边 Σ k = 1 j E k E_i=1+\Sigma^{i与j有返祖边}_{j\in (1,i)}\Sigma_{k=1}^{j}E_k Ei=1+Σj∈(1,i)i与j有返祖边Σk=1jEk
这里第二个累加和可以在边做边处理一个前缀和，至于一个个累加可以直接暴力，因为第一个累加最多只会累加m次（因为只有m个返祖边）时间复杂度为 O ( n + m ) O(n+m) O(n+m)

#include<bits/stdc++.h>
using namespace std;
#define Mod 998244353
const int N=1e6+10;
#define ll long long
int id,n,m;ll f[N],sum[N];
vector<int>fa[N];
int main()
{
	scanf("%d%d%d",&id,&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		fa[u].push_back(v);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<fa[i].size();j++)
		  f[i]=(f[i]+sum[i-1]-sum[fa[i][j]-1]+Mod)%Mod;
		f[i]=(f[i]+fa[i].size()+1)%Mod;sum[i]=(sum[i-1]+f[i])%Mod;
	}printf("%lld",sum[n]);
	return 0;
}