AtCoderBeginnerContest393（ABCDEF）

A - Poisonous Oyster 翻译：

        牡蛎有四种类型，分别为 1、2、3 和 4。其中一种吃了会引起胃病。其他类型的牡蛎吃了不会引起胃病。

        高桥吃了 1 号和 2 号牡蛎，青木吃了 1 号和 3 号牡蛎。每个人是否生病的信息以两个字符串 S 1 和 S2 表示。

        具体来说，S 1 = sick 表示高桥生病了，S 1 = fine 表示高桥没有生病。同样，S 2=sick  表示青木生病，S 2 = fine 表示青木没有生病。

        根据给定信息，找出哪种牡蛎会引起胃病。

思路：

        直接分类讨论：

                sick sick 表示都吃了有病的牡蛎，则1号牡蛎有病毒。

                fine sick 表示高桥没吃有毒牡蛎，青木吃了有病的牡蛎，则3号牡蛎有病毒。

                sick fine 表示高桥吃了有毒牡蛎，青木没吃有病的牡蛎，则2号牡蛎有病毒。

                 fine fine 表示都没吃有病的牡蛎，则4号牡蛎有病毒。

实现： #include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ // 关闭输入输出流同步 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); // 不使用科学计数法 // cout<<fixed; // 中间填保留几位小数，不填默认 // cout.precision(); string s1,s2; cin>>s1>>s2; if (s1=="sick" && s2=="sick"){ cout<<1<<endl; }else if (s1=="sick" && s2=="fine"){ cout<<2<<endl; }else if (s1=="fine" && s2=="sick"){ cout<<3<<endl; }else{ cout<<4<<endl; } } B - A..B..C  翻译：

        给出字符串 S。

        求 S 中有多少处 A、B、C 以相同的间隔依次排列。

        具体地说，求满足以下所有条件的整数 (i,j,k) 三元组的个数。这里，∣S∣ 表示 S 的长度，S x  表示 S 的 x 个字符。

        

思路：

        中心扩展法，从每个点B处向左右搜索是否为A，C。对此计数。

实现： #include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ // 关闭输入输出流同步 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); // 不使用科学计数法 // cout<<fixed; // 中间填保留几位小数，不填默认 // cout.precision(); string s; cin>>s; int cnts = 0,n = s.size(); for (int i=0;i<n;i++){ if (s[i]!='B') continue; for (int j=1;i+j<n && i-j>=0;j++){ cnts+=((s[i-j]=='A') &&(s[i+j]=='C')); } } cout<<cnts<<endl; } C - Make it Simple  翻译：

        给你一个有 N 个顶点和 M 条边的无向图，顶点编号为 1 到 N，边编号为 1 到 M。边i连接点。         要通过删除边使图变得简单，必须删除的边的最少数目是多少？         在这里，当且仅当一个图不包含自循环或多条边时，它才被称为简单图。

思路：

        使用邻接表记录边，删除重边与自循的边。

实现： #include<bits/stdc++.h> using namespace std; using ll = long long; void solve(){ int n,m; cin>>n>>m; set<pair<int,int>> cnts; int ans = 0; for (int u,v,i=1;i<=m;i++) { cin>>u>>v; if (u==v){ ans++; }else { if (u>v) swap(u,v); pair<int,int> now={u,v}; // 里面有 if (cnts.find(now)!=cnts.end()){ ans++; continue; } // cout<<" "<<u<<" "<<v<<endl; cnts.insert(now); } } cout<<ans<<endl; } int main(){ // 关闭输入输出流同步 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); // 不使用科学计数法 // cout<<fixed; // 中间填保留几位小数，不填默认 // cout.precision(); solve(); } D - Swap to Gather   翻译：

        给你一个长度为 N 的字符串 S，其中包含 0 和 1。可以确保S中至少包含一个 1 。

        您可以执行以下操作任意次数（可能为零）：

选择一个整数 i (1≤i≤N-1) 并 交换 S 的第 i 个字符和第 (i+1)-个字符。

        找出使所有 1 都连续的最小操作次数。

        这里，被称为连续1  当且仅当存在整数 l 和 r（1≤l≤r≤N），使得 S 的第 i 个字符为 1，当且仅当 l≤i≤r，否则为 0。

思路：

        在最后连续1的情况下，左边1与右边1的距离之差是固定的，要达到这种情况必然是去除了其内的0，之后不断向内缩1即可。

实现： #include<bits/stdc++.h> using namespace std; using ll = long long; void solve(){ int n; string s; cin>>n; cin>>s; int cnt_1 = 0; for (auto i:s) cnt_1+=(i=='1'); ll ans = 0; for (int l=0,r=n-1;;){ while (l<r && s[l]=='0') l++; while (l<r && s[r]=='0') r--; if (l>=r) break; cnt_1-=2; ans += r-l-1-cnt_1; l++; r--; } cout<<ans<<endl; } int main(){ // 关闭输入输出流同步 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); // 不使用科学计数法 // cout<<fixed; // 中间填保留几位小数，不填默认 // cout.precision(); solve(); }

E - GCD of Subset   翻译：

        你被给予一个长为N的序列和一个正数K(最大为N)。

        对于每个i=1,2,...,N，解决下面的问题：

        当你从A的获取包含的K个元素，找到GCD（最大公共因）最大的可能值。 思路：

        考虑（x为满足条件的值）：

                1. A_i 能被 x 整除。

                2. x有K个及以上的倍数。        

        记录每个数的倍数的数量，遍历以当前数为因数且当前数有K个及以上的倍数，更新倍数的答案。

实现： #include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 1200005; // cnts：记录每个数出现的次数，cnt_fact：被x整除的数的数量 vector<int> cnts(N,0),cnt_fact(N,0); void solve(){ int n,k; cin>>n>>k; vector<int> nums(n); int mx=0; for (int& i:nums){ cin>>i; cnts[i]++; mx = max(mx,i); } // 因子 for (int factor=1;factor<=mx;factor++){ // 被factor整除的数 for (int num=factor;num<=mx;num+=factor){ cnt_fact[factor]+=cnts[num]; } } // ans：每个值满足条件的最大公约数 vector<int> ans(mx+1,0); for (int factor=1;factor<=mx;factor++){ if (cnt_fact[factor]<k) continue; for (int num=factor;num<=mx;num+=factor){ ans[num] = max(ans[num],factor); } } for (int i:nums){ cout<<ans[i]<<"\n"; } } int main(){ // 关闭输入输出流同步 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); // 不使用科学计数法 // cout<<fixed; // 中间填保留几位小数，不填默认 // cout.precision(); solve(); }

F - Prefix LIS Query    翻译：

        你被给予一个长为N的序列。

        回答Q个问题。第 i （）个问题如下：

        你被两个数字。考虑中的子序列严格递增且构成的元素最多为。找到子序列的最大长度。可以确定。 思路：

        使用（贪心+二分）求最长子序列，同时使用离线算法求问题。 

实现： #include<bits/stdc++.h> using namespace std; using ll = long long; // lis(贪心+二分实现)+离线 void solve(){ int n,q; cin>>n>>q; vector<int> a(n); for (int& i:a) cin>>i; // 使用点位来记录问题 vector<vector<pair<int,int>>> query(n); for (int r,x,i=0;i<q;i++){ cin>>r>>x; r--; query[r].emplace_back(x,i); } vector<int> g,ans(q); for (int i=0;i<n;i++){ auto iter = lower_bound(g.begin(),g.end(),a[i]); if (iter==g.end()){ g.push_back(a[i]); }else{ *iter = a[i]; } // 当前点位有哪些询问 for (auto [x,ind]:query[i]){ ans[ind] = upper_bound(g.begin(),g.end(),x)-g.begin(); } } for (int& i:ans){ cout<<i<<"\n"; } } int main(){ // 关闭输入输出流同步 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); // 不使用科学计数法 // cout<<fixed; // 中间填保留几位小数，不填默认 // cout.precision(); solve(); }

  有建议可以评论，我会积极改进qwq。