「CF1280X」Codeforces Round #607 (Div. 1)

2019年12月24日6,8190

A. Cut and Paste

长度在 x 范围内，直接模拟字符串合成，达到 x 范围外直接通过计数得到答案

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T, x, n;
string str;
int main()
{
    T = read();
    while(T--)
    {
        x = read();
        cin >> str;
        ll ans = str.length();
        for(int i = 0; i < x; i++)
        {
            int t = str[i] - '0';
            if(str.length() < x)
            {
                string c = str.substr(i + 1, str.length() - i - 1);
                for(int j = 0; j < t - 1; j++)
                    str += c;
                ans = str.length();
            }
            else
            {
                int tmp = (ans - i - 1 + mod) % mod;
                for(int j = 0; j < t - 1; j++)
                    ans = (ans + tmp) % mod;
            }
            // cout << str << endl;
        }
        // cout << str.length() <<' '<<str << endl;
        cout << ans << endl;
    }
    return 0;
}

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T, x, n;

string str;

int main()

{

T = read();

while(T--)

{

x = read();

cin >> str;

ll ans = str.length();

for(int i = 0; i < x; i++)

{

int t = str[i] - '0';

if(str.length() < x)

{

string c = str.substr(i + 1, str.length() - i - 1);

for(int j = 0; j < t - 1; j++)

str += c;

ans = str.length();

}

else

{

int tmp = (ans - i - 1 + mod) % mod;

for(int j = 0; j < t - 1; j++)

ans = (ans + tmp) % mod;

}

// cout << str << endl;

}

// cout << str.length() <<' '<<str << endl;

cout << ans << endl;

}

return 0;

}

B. Beingawesomeism

首先答案不超过 4，分类讨论一下 1 2 3 的情况，其中 2 有两种情况：

有角上的点，有整行 / 列的点

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T, r, c;
int a[65][65], f1[65], f2[65];
string s;
int main()
{
    T = read();
    while(T--)
    {
        r = read(); c = read();
        memset(f1, 0, sizeof(f1));
        memset(f2, 0, sizeof(f2));
        memset(a, 0, sizeof(a));
        bool hav_A = 0, hav_P = 0;
        for(int i = 0; i < r; i++)
        {
            cin >> s;
            for(int j = 0; j < c; j++)
                if(s[j] == 'A')
                {
                    hav_A = 1, f1[i]++, f2[j]++;
                    a[i][j] = 1;
                }
                else
                    hav_P = 1;
        }
        if(!hav_A)
        {
            puts("MORTAL");
            continue;
        }
        if(!hav_P)
        {
            puts("0");
            continue;
        }
        bool fullc = 0;
        for(int i = 0; i < r; i++)
            if(f1[i] == c)fullc = 1;
        for(int i = 0; i < c; i++)
            if(f2[i] == r)fullc = 1;        
        int ans = 4;
        if(f1[0] == c || f1[r - 1] == c || f2[0] == r || f2[c - 1] == r)
            ans = 1;
        else if(a[0][0] || a[0][c - 1] || a[r - 1][0] || a[r - 1][c - 1] || fullc)
            ans = 2;
        else if(f1[0] || f1[r - 1] || f2[0] || f2[c - 1])
            ans = 3;
        cout << ans << endl;
        // cout << fullc << endl;
    }
    return 0;
}

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T, r, c;

int a[65][65], f1[65], f2[65];

string s;

int main()

{

T = read();

while(T--)

{

r = read(); c = read();

memset(f1, 0, sizeof(f1));

memset(f2, 0, sizeof(f2));

memset(a, 0, sizeof(a));

bool hav_A = 0, hav_P = 0;

for(int i = 0; i < r; i++)

{

cin >> s;

for(int j = 0; j < c; j++)

if(s[j] == 'A')

{

hav_A = 1, f1[i]++, f2[j]++;

a[i][j] = 1;

}

else

hav_P = 1;

}

if(!hav_A)

{

puts("MORTAL");

continue;

}

if(!hav_P)

{

puts("0");

continue;

}

bool fullc = 0;

for(int i = 0; i < r; i++)

if(f1[i] == c)fullc = 1;

for(int i = 0; i < c; i++)

if(f2[i] == r)fullc = 1;

int ans = 4;

if(f1[0] == c || f1[r - 1] == c || f2[0] == r || f2[c - 1] == r)

ans = 1;

else if(a[0][0] || a[0][c - 1] || a[r - 1][0] || a[r - 1][c - 1] || fullc)

ans = 2;

else if(f1[0] || f1[r - 1] || f2[0] || f2[c - 1])

ans = 3;

cout << ans << endl;

// cout << fullc << endl;

}

return 0;

}

C. Jeremy Bearimy

考虑一条边，如果一侧有奇数个点，这条边至少计入结果一次

一条边计入结果的最大次数是两侧点个数的较小值，为什么所有边都能达到这个较小值？假设一条边一侧有 a 个点，另一侧有 b 个点，a < b，可以把这 2a 个点配对的点安排得离这条边比较近来构造

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T, n;
vector<int> e[200005], v[200005];
int size[200005];
ll G, B;
void dp(int x, int fa)
{
    size[x] = 1;
    for(int i = 0; i < e[x].size(); i++)
        if(e[x][i] != fa)
        {
            int y = e[x][i], w = v[x][i];
            dp(y, x);
            size[x] += size[y];
            if(size[y] & 1)
                G += w;
            B += (ll)w * min(size[y], n - size[y]);
        }
}
int main()
{
    T = read();
    while(T--)
    {
        n = read(); n *= 2;
        for(int i = 1; i <= n; i++)
        {
            e[i].clear();
            v[i].clear();
        }
        G = B = 0;
        for(int i = 1; i < n; i++)
        {
            int x = read(), y = read(), w = read();
            e[x].push_back(y);
            e[y].push_back(x);
            v[x].push_back(w);
            v[y].push_back(w);
        }
        dp(1, 0);
        cout << G <<' '<< B << endl;
    }
    return 0;
}

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T, n;

vector<int> e[200005], v[200005];

int size[200005];

ll G, B;

void dp(int x, int fa)

{

size[x] = 1;

for(int i = 0; i < e[x].size(); i++)

if(e[x][i] != fa)

{

int y = e[x][i], w = v[x][i];

dp(y, x);

size[x] += size[y];

if(size[y] & 1)

G += w;

B += (ll)w * min(size[y], n - size[y]);

}

int main()

{

T = read();

while(T--)

{

n = read(); n *= 2;

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

{

e[i].clear();

v[i].clear();

}

G = B = 0;

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

{

int x = read(), y = read(), w = read();

e[x].push_back(y);

e[y].push_back(x);

v[x].push_back(w);

v[y].push_back(w);

}

dp(1, 0);

cout << G <<' '<< B << endl;

}

return 0;

}

« 「CF1276X」Codeforces Round #606 (Div. 1)

hzwer.com _ Home | http://hzwer.com

「CF1280X」Codeforces Round #607 (Div. 1)

分类目录

热门文章

Myfriends

近期评论