danihao123's Blog

[BZOJ 3725]Matryca

很有意思的思考题。

这道题通过特殊情况我们可以猜想，假设最近两个不同色块距离为[tex]x[/tex]（这是半闭半开序列长度），则答案为[tex]n-x+1[/tex]。然而事实就是如此。

代码：

/**************************************************************
    Problem: 3725
    User: danihao123
    Language: C++
    Result: Accepted
    Time:216 ms
    Memory:1796 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000001;
char buf[maxn];
int main(){
    int n;
    register int i,now;
    char last_s=0;
    scanf("%s",buf);
    n=strlen(buf);
    register int ans=n;
    for(i=0;i<n;i++){
        if(buf[i]!='*'){
            if(last_s){
                if(buf[i]!=last_s){
                    ans=min(ans,i-now);
                    last_s=buf[i];
                    now=i;
                }else{
                    now=i;
                }
            }else{
                last_s=buf[i];
                now=i;
            }
        }
    }
    printf("%d\n",n-ans+1);
    return 0;
}

[CF 676B]Pyramid of Glasses

这题可以直接模拟，貌似也可过。但复杂度很高。

我们可以直接把t个单位的酒放入第一个杯，然后向下溢出，以此类推，这样复杂度就很优秀了。

代码：

#include <iostream>
using namespace std;
const int maxn=12;
int n;
long double k[maxn][maxn];
int call(int x){
	int i,ans=0;
	long double temp;
	if(x>n)
		return 0;
	for(i=1;i<=n;i++){
		if(k[x][i]>=1.0){
			ans++;
			if(k[x][i]>1.0 && x<n){
				temp=(k[x][i]-1.0)/2;
				k[x][i]=1.0;
				k[x+1][i]+=temp;
				k[x+1][i+1]+=temp;
			}
		}
	}
	return ans+call(x+1);
}
int main(){
	cin>>n>>k[1][1];
	cout<<call(1)<<endl;
	return 0;
}