真的太菜了……
// Problem: A. Cover in Water // Contest: Codeforces - Codeforces Round 911 (Div. 2) // URL: https://codeforces.com/contest/1900/problem/0# // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<iostream> #include<algorithm> #include<cmath> #include<vector> #include<map> #include<queue> #include<deque> #include<stack> #include<set> #include<utility> #include<iomanip> #include<string> #define int long long #define endl '\n' using namespace std; const int N=100010; //cout << fixed << setprecision(2) << 3.1415 << endl; //cin.tie(nullptr)->s ync_with_stdio(0); bool cmp(int x,int y){ return x>y; } void solve(){ int n; cin>>n; char s[102]; s[0]='#'; s[n+1]='#'; for(int i=1;i<=n;i++){ cin>>s[i]; } int ans=0; for(int i=1;i<=n;i++){ if((s[i]=='.'&&s[i+1]=='#')||(s[i]=='.'&&s[i-1]=='#')){ ans++; } if(s[i]==s[i+1]&&s[i+1]==s[i+2]&&s[i]=='.'){ ans=2; break; } } cout<<ans<<"\n"; // int n,cnt=0,ans=0,cnt2=0; // cin>>n; // // vector<int> v; // string a[105]; // a[0]='.',a[n+1]='#'; // for(int i=0;i<n;i++){ // cin>>a[i]; // if(a[i]==a[i+1]&&a[i+1]==a[i+2]&&a[i]=='.')ans=2; // if((a[i]=="."&&a[i+1]=="#")||(a[i]=="#"&&a[i+1]==".")) ans++; // // if(a[i]==".") cnt++; // // else{ // // cnt2++; // // v.push_back(cnt); // // cnt=0; // // } // // sort(v.begin(),v.end(),cmp); // // if(v[0]>=3) ans=2; // // else ans=cnt2-1; // } // cout<<ans<<endl; } signed main(){ int _=1; cin>>_; while(_--) solve(); return 0; }
一开始分析完找到的规律是:
1.只要有超过三个连续的“.”存在,输出的答案就一定是2,因为位于中间位置的水可以无限次被拿出来放到其他地方,拿走后就一定会自动补充出新的中间位置的水。
2.有多少个“#”就有(多少-1)个
吕文钦的(真的很强……):
两种情况的特判,但是对数组两端的情况进行了限定,因为题目就是相当于两边是不能加水的,限定后可以做到与题目一致。
对“连续三个”的处理:我是计数、分别存进vector然后排序看最大的是否大于等于3,他直接利用连续三个元素的相等情况进行判断,确实是省去很大工作量
“#.”和“.#”的情况都是计数器加一,因为本身就是在三个连续这种情况之外,所以一定需要加一次水