codeforces#754(div2)A~D题解

简介: codeforces#754(div2)A~D题解

这场cf,结论加思维居多。想的道就能秒写,比赛开始1分钟后,A题ac了,第4分钟B题ac了,然后第11分钟交了c,wa了,第33分钟后ac了,没有想会可以直接找字符串,wa了几发,后面暴力直接通过,在这里我挖了一下好的c题代码,然后就是D题,第一眼,看到树,我有点慌,后面看完题目,第53分钟左右ac了。最后比赛还有一个多小时,去刷题去了。写不来E,F。

E,F待补。


A.M. Deviation


题意,就是找三个数,然后按照他给的规则找最小值。


#include <bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(0);cin.tie(0);
  int t;
  cin>>t;
  while (t--)
  {
    int x,y,z,s;
    cin>>x>>y>>z;
    s=x+y+z;
    x=s/3;y=s/3;z=s-x-y;
    if (z-y==2) --z,++y;
    cout<<abs(x+z-2*y)<<'\n';
  }
}


B.

题意就是,给一个串,然后把他变成单调不递减的,要求你用一个子串(单独不递增)的使输入的串变成不递减的,很显然答案只会有0和1;


#include <bits/stdc++.h>
using namespace std;
int st[1002],tp;
int main()
{
  ios::sync_with_stdio(0);cin.tie(0);
  int t;
  cin>>t;
  while (t--)
  {
    int n,cnt=0;tp=0;
    string s;
    cin>>n>>s;
    int i;
    for (i=0;i+1<n;i++) if (s[i]>s[i+1]) break;
    if (i+1==n) {cout<<"0\n";continue;}
    cout<<"1\n";
    for (i=0;i<n;i++) cnt+=s[i]=='0';
    for (i=0;i<cnt;i++) if (s[i]=='1') st[++tp]=i+1;
    for (i=cnt;i<n;i++) if (s[i]=='0') st[++tp]=i+1;
    cout<<tp;
    for (i=1;i<=tp;i++) cout<<' '<<st[i];cout<<'\n';
  }
}


C.


题意就是找一个a的数量比b或者c数量多的最长子串,我们可以删前面和后面的字符串来得到这个子串。

最后就是查找固定子串判断就行。

#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t--) {
    string s;
    int n;
    cin >> n >> s;
    if (s.find("aa") < n)
      puts("2");
    else if (s.find("aba") < n || s.find("aca") < n)
      puts("3");
    else if (s.find("abca") < n || s.find("acba") < n)
      puts("4");
    else if (s.find("abbacca") < n || s.find("accabba") < n)
      puts("7");
    else
      puts("-1");
  }
}


D

类似二分图,然后结论个数就是n,我们要找一个最多的点要求先手的人能赢,并且要通过

  • u⊕v≤min(u,v)这个条件。
  • 最后我们建一个树,然后用a[0],a[1]来代表二分图存点。通过深搜来赋值,就行了。


#include <bits/stdc++.h>
using namespace std;
const int N=2.1e5;
vector<int> e[N],a[2];
int dep[N],p[N];
void dfs(int u)
{
  a[dep[u]&1].push_back(u);
  for (auto &v:e[u]) if (!dep[v])
  {
    dep[v]=dep[u]+1;
    dfs(v);
  }
}
int main()
{
  ios::sync_with_stdio(0);cin.tie(0);
  int t;
  cin>>t;
  while (t--)
  {
    int n,i,j;
    cin>>n;
    memset(dep+1,0,n*sizeof dep[0]);
    for (i=0;i<=1;i++) a[i].clear(),a[i].reserve(n);
    for (i=1;i<=n;i++) e[i].clear();
    for (i=1;i<n;i++)
    {
      int u,v;
      //u=i+1;v=rand()%i+1;
      cin>>u>>v;
      e[u].push_back(v);e[v].push_back(u);
    }
    dfs(dep[1]=1);
    if (a[0].size()<a[1].size()) swap(a[0],a[1]);
    for (i=1;i<=n;i<<=1);
    i>>=1;
    for (j=i;j<=n;j++) p[a[0].back()]=j,a[0].pop_back();
    for (i=0;i<20;i++) if (a[0].size()>>i&1) for (j=1<<i;j<1<<i+1;j++) p[a[0].back()]=j,a[0].pop_back();
    for (i=0;i<20;i++) if (a[1].size()>>i&1) for (j=1<<i;j<1<<i+1;j++) p[a[1].back()]=j,a[1].pop_back();
    for (i=1;i<=n;i++) for (auto &v:e[i]) assert((p[i]^p[v])>min(p[i],p[v]));
    for (i=1;i<=n;i++) cout<<p[i]<<" \n"[i==n];
  }
}


相关文章
|
6月前
|
C++
【洛谷 P1923】【深基9.例4】求第 k 小的数 题解(nth_element)
该题目要求输入一个奇数个整数 $n$($1 \le n &lt; 5000000$)和一个位置 $k$,在给定的 $n$ 个不超过 ${10}^9$ 的整数中找出第 $k$ 小的数。样例输入为 `5 1` 和 `4 3 2 1 5`,输出第 $1$ 小的数,即 `2`。解决方案使用 C++ 的 `nth_element` 函数来找到第 $k$ 小的数。
56 0
|
6月前
【CodeForces】Codeforces Round 857 (Div. 2) B
【CodeForces】Codeforces Round 857 (Div. 2) B
136 0
Codeforces Round 859 (Div. 4)题解
Codeforces Round 859 (Div. 4)题解
106 0
【算法题解】Codeforces Round #817 (Div. 4)题解
【算法题解】Codeforces Round #817 (Div. 4)题解
【算法题解】Codeforces Round #817 (Div. 4)题解
|
人工智能 BI
Codeforces Round #805 (Div. 3) 题解
Codeforces Round #805 (Div. 3) 题解
Codeforces Round #805 (Div. 3) 题解
|
人工智能 索引
Codeforces Round #806 (Div. 4) 题解
Codeforces Round #806 (Div. 4) 题解