[ABC189] AtCoder Beginner Contest 189

[ABC189] AtCoder Beginner Contest 189

Tasks

---

	Task Name	Time Limit	Memory Limit
A	Slot	2 sec	1024 MB	Submit
B	Alcoholic	2 sec	1024 MB	Submit
C	Mandarin Orange	1.5 sec	1024 MB	Submit
D	Logical Expression	2 sec	1024 MB	Submit
E	Rotate and Flip	2 sec	1024 MB	Submit
F	Sugoroku2	2 sec	1024 MB	Submit

Solution

Editorial on AtCoder

A - Slot

模拟

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

string s;

int main()
{
//	freopen("1.in","r",stdin);
	cin>>s;
	for(int i=1;i<(int)s.length();i++) 
		if(s[i]!=s[0]) {
			puts("Lost");
			return 0;
		}
	puts("Won");
	return 0;
}

B - Alcoholic

同样是模拟，不过要化小数为整数，卡精度差评。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

int n,m;

int main()
{
//	freopen("1.in","r",stdin);
	int x,y;
	cin>>n>>m;
	m*=100;
	for(int i=1;i<=n;i++) {
		cin>>x>>y;
		if(m<y*x) {
			cout<<i<<endl;
			return 0;
		}
		m-=y*x;
	}
	cout<<"-1"<<endl;
	return 0;
}

C - Mandarin Orange

AcWing 131. 直方图中最大的矩形

#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=2e5+5;

int n;
int a[N];
int r[N],l[N];

stack<int> S;

int main()
{
//	freopen("1.in","r",stdin);
	int i,x;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++) 
		scanf("%d",&a[i]);
	
	for(i=1;i<=n;i++) {
		while(S.size() && a[i]<a[S.top()]) {
			x=S.top(); S.pop();
			r[x]=i-1;
		}
		S.push(i);
	}
	while(S.size()) r[S.top()]=n,S.pop();
	
	for(i=n;i>=1;i--) {
		while(S.size() && a[i]<a[S.top()]) {
			x=S.top(); S.pop();
			l[x]=i+1;
		}
		S.push(i);
	}
	while(S.size()) l[S.top()]=1,S.pop();
	
	int ans=0;
	for(i=1;i<=n;i++) 
		ans=max(ans,(r[i]-l[i]+1)*a[i]);
	printf("%d
",ans);
	return 0;
}

D - Logical Expression

Dp.

考虑 (f[i][0/1]) 表示运算到第 i 位值为 (0/1) 的方案数，按照定义转移即可。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=100+5;

int n;
LL f[N][2];
string s[N];

int main()
{
//	freopen("1.in","r",stdin);
	int i;
	cin>>n;
	for(i=1;i<=n;i++) 
		cin>>s[i];
	
	f[0][0]=f[0][1]=1;
	for(i=1;i<=n;i++) {
		if(s[i]=="AND") {
			// if this state is 0
			f[i][0]+=f[i-1][0]+f[i-1][1];
			// if this state is 1
			f[i][0]+=f[i-1][0];
			f[i][1]+=f[i-1][1];
		}
		
		else {
			// if this state is 0
			f[i][0]+=f[i-1][0];
			f[i][1]+=f[i-1][1];
			// if this state is 1
			f[i][1]+=f[i-1][0]+f[i-1][1];
		}
	}
	
	cout<<f[n][1]<<endl;
	return 0;
}

E - Rotate and Flip

对坐标的旋转，翻转。

维护 (mtx,mty,atx,aty,rev) , 使得 初始坐标为 ((x,y)) 代入得到结束坐标 ((mtx*x+atx,mty*y+aty)) .

如果 (rev==1) 还需把 (x,y) 对调一下。

对于操作，递推即可。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL,LL> PLL;
typedef PLL Point;

#define x first
#define y second

const int N=2e5+5;

int n,m,Q;

bool rev[N];
LL mtx[N],atx[N],mty[N],aty[N];

Point a[N];

int main()
{
//	freopen("1.in","r",stdin);
	int i;
	int opt;
	LL p;
	int x,y;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++) 
		scanf("%lld%lld",&a[i].x,&a[i].y);
	
	mtx[0]=1,mty[0]=1;
	scanf("%d",&m);
	for(i=1;i<=m;i++) {
		scanf("%d",&opt);
		if(opt==1) {
			rev[i]=(rev[i-1]^1);

			mtx[i]=mty[i-1],atx[i]=aty[i-1];
			mty[i]=-mtx[i-1],aty[i]=-atx[i-1];
		}
		else if(opt==2) {
			rev[i]=(rev[i-1]^1);
			
			mtx[i]=-mty[i-1]; atx[i]=-aty[i-1];
			mty[i]=mtx[i-1]; aty[i]=atx[i-1];
		}
		else if(opt==3) {
			scanf("%lld",&p);
			rev[i]=rev[i-1];
			mtx[i]=-mtx[i-1]; atx[i]=-atx[i-1]+2*p;
			mty[i]=mty[i-1]; aty[i]=aty[i-1];
		}
		else {
			scanf("%lld",&p);
			rev[i]=rev[i-1];
			mtx[i]=mtx[i-1]; atx[i]=atx[i-1];
			mty[i]=-mty[i-1]; aty[i]=-aty[i-1]+2*p;			
		}
		
//		printf("%lld %lld , %lld %lld , %d
",mtx[i],atx[i],mty[i],aty[i],(rev[i]==true));
	}
	
	scanf("%d",&Q);
	while(Q--) {
		scanf("%d%d",&x,&y);
		if(!rev[x]) 
			printf("%lld %lld
",a[y].x*mtx[x]+atx[x],a[y].y*mty[x]+aty[x]);
		else printf("%lld %lld
",a[y].y*mtx[x]+atx[x],a[y].x*mty[x]+aty[x]);
	}
	return 0;
}

F - Sugoroku2

这题卡了我一个多小时。

刚开始还以为要高斯消元，后来发现可以维护一个 (real[i]=f[i]+g[i] imes real[0]) , 最后手动消元。

我很自然地写了一个顺推，就 WA 了。

后来数篇题解都是逆推....后来我才知道有一个叫 概率正推，期望逆推 的东西。

• 期望DP到底为啥逆推 - starsing - 博客园
• （概率DP）正向推概率，反向推期望_nameofcsdn的博客-CSDN博客

具体适用场景是结局一定的递推期望和概率。

我的理解是 因为

[f[i]=frac{sum_{j=i-m}^{i-1} f[j]}{m}+1 ]

里的 (f[j]) 不一定都存在，即从 (0) 出发不一定都能到 (j), 而 期望是对所有可能情况的步长的带权平均，所以不能正着推。

从已知结果逆推就没有这方面的顾虑。

Code ：

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N=2e5+5;

int n,m,k;
double f[N],g[N];
// f[i]+g[i]*f[0] 表示 i 到 >=n 的期望步数。
 
int a[N];
bool st[N];

bool check()
{
	static int t[N];
	memset(t,0,sizeof t);
	
	t[0]=1; 
	int cur=1;
	for(int i=1;i<n+m;i++) {
		int prev=i-m-1;
		if(prev>=0) cur-=t[prev];
		
		if(st[i]) continue;
		else t[i]=(cur>0);
		cur+=t[i];
	}
	for(int i=n;i<n+m;i++) 
		if(t[i]) return true;
	return false;
}

int main()
{
//	freopen("1.in","r",stdin);
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++) {
		cin>>a[i];
		st[a[i]]=true;
	}
	if(!check()) {
		puts("-1");
		return 0;
	}
	
	double sumf=0,sumg=0;
	for(int i=n-1;i>=0;i--) {
		sumf=sumf-f[i+m+1]+f[i+1];
		sumg=sumg-g[i+m+1]+g[i+1];
		
		if(st[i]) f[i]=0,g[i]=1;
		else {
			f[i]=sumf/m+1;
			g[i]=sumg/m;
		}
	}	
	
	// f[0]=f[0].cur+g[0]*f[0];
	double ans=f[0]/(1-g[0]);
	printf("%.4lf
",ans);
}