Codeforces Div3 #498 A-F

A. Adjacent Replacements

执行1e9次命令，输出的最后数组的样子

一个奇数执行两次命令会变回原来的数字

一个偶数只会执行一次命令变成比自身小1的数

#include<bits/stdc++.h>

#define int long long

#define MAX(a,b,c) max(a,max(b,c))

#define MIN(a,b,c) min(a,min(b,c))

#define pb push_back

#define fi first

#define se second

typedef long long ll;

typedef long long LL;

typedef unsigned long long ull;

typedef unsigned long long uLL;

using namespace std;

const int maxn=1e6+;

const int INF=1e15;

int a[maxn];

int32_t main()

{

   int n; cin>>n;

   for(int i=;i<=n;i++) cin>>a[i];

   for(int i=;i<=n;i++)

   {

       if(a[i]%==) cout<<a[i]<<" ";

       else          cout<<a[i]-<<" ";

   }

}

A.cpp

B. Polycarp's Practice

给出数组n k 将数组分成k段（每段至少1）求k段每段中最大数的和的最大值

排序一下最大的n个数就是数字最大的

将k个最大数标记我用的map 标记

然后扫一遍输出第一个标记前的非标记的个数和自身标记和标记间的个数最后一个标记和标记间还有标记后的个数

例子

1 2 3 2 1 4 1 5 1 3

mp[3]=1; mp[2]=1; mp[5]=1; 这是被标记的

分成的为 1 2 3 2 1 4 1 5 1 3 三段

#include<bits/stdc++.h>

#define int long long

#define MAX(a,b,c) max(a,max(b,c))

#define MIN(a,b,c) min(a,min(b,c))

#define pb push_back

#define fi first

#define se second

typedef long long ll;

typedef long long LL;

typedef unsigned long long ull;

typedef unsigned long long uLL;

using namespace std;

const int maxn=1e6+;

const int INF=1e15;

int a[maxn];

int b[maxn];

map<int,int> mp;

int32_t main()

{

   int n,k; cin>>n>>k;

   for(int i=;i<=n;i++) {cin>>a[i]; b[i]=a[i];}

   sort(a+,a++n);

   int ans=; int num=k;

   for(int i=n;i>=;i--)

   {

       if(num) {ans+=a[i]; num--; mp[a[i]]++; }

   }

   cout<<ans<<endl;

   int t=;

   for(int i=;i<=n;i++)

   {

       if(mp[b[i]]&&k!=)

       {

           cout<<t+<<" ";  t=; mp[b[i]]--; k--;

       }

       else

       {

           t++;

       }

   }

   cout<<t<<" ";

}

B.cpp

C. Three Parts of the Array

给你一个数组你分成3段（长度可以为0）是第一段和最后一段的和相等求怎么样分让第一段和最大

定义 num1=num3=0;

一个从前往后找一个从后往前找谁少谁加一样就记录答案都加一个数

#include<bits/stdc++.h>

#define int long long

#define MAX(a,b,c) max(a,max(b,c))

#define MIN(a,b,c) min(a,min(b,c))

#define pb push_back

#define fi first

#define se second

typedef long long ll;

typedef long long LL;

typedef unsigned long long ull;

typedef unsigned long long uLL;

using namespace std;

const int maxn=1e6+;

const int INF=1e15;

int a[maxn];

int32_t main()

{

   int n; cin>>n;

   for(int i=;i<=n;i++) scanf("%d",&a[i]);

   int num1=;

   int num3=;

   int ans=;

   int i=;

   int j=n+;

   while(i+!=j)

   {

       if(num1==num3)

       {

           ans=max(num1,num3); if(i+==j) break;

           i++;j--; num1+=a[i]; num3+=a[j];

       }

       else if(num1<num3)

       {

           i++; num1+=a[i];

       }

       else if(num1>num3)

       {

           j--; num3+=a[j];

       }

   }

   if(num1==num3) ans=num1;

   cout<<ans<<endl;

}

C.cpp

D. Two Strings Swaps

给你两个字符串长度一样修改第一个字符串再通过变换让两个字符串一样

变换规则

Choose any index ii (1≤i≤n1≤i≤n) and swap characters aiai and bibi;
Choose any index ii (1≤i≤n1≤i≤n) and swap characters aiai and an−i+1an−i+1;
Choose any index ii (1≤i≤n1≤i≤n) and swap characters bibi and bn−i+1bn−i+1；

找 ai a(n-i) bi ,b(n-i) 中最大有多少对字符一样

当ai=a(n-i) 时特判 bi！=b(n-1) 要修改两个

#include<bits/stdc++.h>

#define int long long

#define MAX(a,b,c) max(a,max(b,c))

#define MIN(a,b,c) min(a,min(b,c))

#define pb push_back

#define fi first

#define se second

typedef long long ll;

typedef long long LL;

typedef unsigned long long ull;

typedef unsigned long long uLL;

using namespace std;

const int maxn=1e6+;

const int INF=1e15;

int32_t main()

{

   int n; cin>>n;

   string ss;cin>>ss;

   string tt;cin>>tt;

   int ans=;

       for(int i=;i<n/;i++)

       {

           int t=;

           if(ss[i]==ss[n--i]) t++;

           if(tt[i]==tt[n--i]) t++;

           else t--;

           int w=;

           if(ss[i]==tt[i]) w++;

           if(ss[n--i]==tt[n--i]) w++;

           int k=;

           if(ss[i]==tt[n--i]) k++;

           if(ss[n-i-]==tt[i]) k++;

           int num=MAX(t,w,k);

           if(num==) ans+=;

           if(num==) ans+=;

       }

   if(n%==)

   {

       if(ss[n/]!=tt[n/]) ans++;

   }

   cout<<ans<<endl;

}

D.cpp

E. Military Problem

树不会很会表述（大家多多见谅）

有一个树

q次询问问节点 x 是否有 y 个子节点没有输出 -1 有输出第y个字节点上的书

#include<bits/stdc++.h>

#define int long long

#define MAX(a,b,c) max(a,max(b,c))

#define MIN(a,b,c) min(a,min(b,c))

#define pb push_back

#define fi first

#define se second

typedef long long ll;

typedef long long LL;

typedef unsigned long long ull;

typedef unsigned long long uLL;

using namespace std;

const int maxn=1e6+;

const int INF=1e15;

vector<int> tree[maxn];

int vis[maxn];

int sum[maxn];

int s[maxn];

int cnt=;

int dfs(int id)

{

    int ans=;

    vis[id]=cnt;

    s[cnt]=id;

    cnt++;

    for(int i=;i<tree[id].size();i++)

        ans+=dfs(tree[id][i]);

    return sum[id]+=ans;

}

int32_t main()

{

    int n,p; cin>>n>>p;

    for(int i=;i<=n;i++)

    {

        int a; cin>>a; tree[a].pb(i);

    }

    dfs();

    while(p--)

    {

        int x,y;

        cin>>x>>y;

        if(sum[x]<y) cout<<"-1"<<endl;

        else

            cout<<s[vis[x]+y-]<<endl;

    }

}

E.cpp

F. Xor-Paths

从（1，1）到（n, m）找路径中所有数的异或为k的道路条数（只能下右）

直接dfs会超时用两端dfs

#include<bits/stdc++.h>

#define int long long

#define MAX(a,b,c) max(a,max(b,c))

#define MIN(a,b,c) min(a,min(b,c))

#define pb push_back

#define fi first

#define se second

typedef long long ll;

typedef long long LL;

typedef unsigned long long ull;

typedef unsigned long long uLL;

using namespace std;

const int maxn=+;

const int INF=0x3f3f3f3f;

int a[][];

map<int,int> mp[][];

int n,m,k;

int MAX;

int ans;

void dfs1(int x,int y,int num)

{

    num=num^a[x][y];

    if(x+y==MAX)

    {

        mp[x][y][num]++;

    }

    else

    {

        int x1=x+;

        int y1=y;

        if(x1>= && x1<=n && x1>= && y1<=m)

        {

            dfs1(x1,y1,num);

        }

        int x2=x;

        int y2=y+;

        if(x2>= && x2<=n && x2>= && y2<=m)

        {

            dfs1(x2,y2,num);

        }

    }

}

void dfs2(int x,int y,int num)

{

    if(x+y==MAX)

    {

        ans+= mp[x][y][num];

    }

    else

    {

        num=num^a[x][y];

        int x1=x-;

        int y1=y;

        if(x1>= && x1<=n && x1>= && y1<=m)

        {

            dfs2(x1,y1,num);

        }

        int x2=x;

        int y2=y-;

        if(x2>= && x2<=n && x2>= && y2<=m)

        {

            dfs2(x2,y2,num);

        }

    }

}

int32_t main()

{

    cin>>n>>m>>k;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            cin>>a[i][j];

        }

    }

    if(n==&&m==)

    {

        if(k==a[][]) cout<<<<endl;

        else cout<<<<endl;

        return ;

    }

    MAX=max(n,m);

    dfs1(,,);

    dfs2(n,m,k);

    cout<<ans<<endl;

}

F.cpp

巴特西

Codeforces Div3 #498 A-F

最新文章

热门文章