[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; }
[BZOJ 1192]鬼谷子的钱袋
这题真是interesting极了!
建议先在纸上实践一下,然后你会发现问题的解就是n的二进制长度!
让我偷着乐一会
[要证明?我这先挖个坑]
代码:
[BZOJ 2456]mode
原来这就是BT众数题的始祖啊~
首先讲一下方法(这种方法其实叫摩尔投票法):