「CF1254X」Codeforces Round #601 (Div. 1)

2019年11月20日4,6591

A. Feeding Chicken

记 R 的数量是 tot 个，则有 tot % k 只鸡的地盘是 tot / k + 1, 其它是 tot / k，蛇形对方格进行染色，把连续的若干个 R 以及它们之间的方格染成一个颜色

#include<map>
#include<set>
#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;
int n, m, k;
char ch[105][105];
int ans[105][105];
int num[105];
char t[105];
int main()
{
    for(int i = 1; i <= 26; i++)
        t[i + 10] = (i - 1) + 'a';
    for(int i = 1; i <= 26; i++)
        t[i + 36] = (i - 1) + 'A';
    for(int i = 1; i <= 10; i++)
        t[i] = '0' + i - 1;
    T = read();
    while(T--)
    {
        n = read(); m = read(); k = read();
        int tot = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%s", ch[i] + 1);
            for(int j = 1; j <= m; j++)
                if(ch[i][j] == 'R')
                    tot++;
        }
        int p = tot / k, q = tot % k;
        for(int i = 1; i <= k; i++)
            if(i <= q)
                num[i] = p + 1;
            else num[i] = p;
        int now = 1;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                int k = j;
                if(i & 1)
                    k = m - j + 1;
                if(ch[i][k] == 'R')
                {
                    if(num[now] == 0)
                        now++;
                    num[now]--;
                }
                ans[i][k] = now;
            }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
                cout << t[ans[i][j]];
            cout << endl;
        }        
    }
    return 0;
}

#include<map>

#include<set>

#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;

int n, m, k;

char ch[105][105];

int ans[105][105];

int num[105];

char t[105];

int main()

{

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

t[i + 10] = (i - 1) + 'a';

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

t[i + 36] = (i - 1) + 'A';

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

t[i] = '0' + i - 1;

T = read();

while(T--)

{

n = read(); m = read(); k = read();

int tot = 0;

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

{

scanf("%s", ch[i] + 1);

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

if(ch[i][j] == 'R')

tot++;

}

int p = tot / k, q = tot % k;

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

if(i <= q)

num[i] = p + 1;

else num[i] = p;

int now = 1;

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

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

{

int k = j;

if(i & 1)

k = m - j + 1;

if(ch[i][k] == 'R')

{

if(num[now] == 0)

now++;

num[now]--;

}

ans[i][k] = now;

}

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

{

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

cout << t[ans[i][j]];

cout << endl;

}

return 0;

}

B2. Send Boxes to Alice (Hard Version)

求和，枚举和的所有质因子 p，从左到右依次贪心，每个箱子里的巧克力数调整为最近的一个 p 的倍数，差的部分从下一个箱子拿

#include<map>
#include<set>
#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 9000000000000000000LL
#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 n;
ll tot, mn;
ll a[1000005], b[1000005];
bool mark[1000005];
void cal(ll x)
{
    if(x == 1)return;
    ll ans = 0;
    for(int i = 1; i <= n; i++)
        b[i] = a[i];
    for(int i = 1; i <= n; i++)
    {
        ll t = b[i] % x;
        if(t > abs(t - x))
            t = t - x;
        b[i + 1] += t;
        ans += abs(t);
    }
    if(ans >= mn)
        return;
    mn = min(mn, ans);
}
int main()
{
    mn = inf;
    n = read();
    for(int i = 1; i <= n; i++)
    {
        a[i] = read();
        tot += a[i];
    }
    if(tot == 1)
    {
        puts("-1");
        return 0;
    }
    for(int i = 2; i <= sqrt(tot); i++)
        if(tot % i == 0)
        {
            cal(i);
            while(tot % i ==0)
                tot /= i;
        }
    cal(tot);        
    cout << mn << endl;
    return 0;
}

#include<map>

#include<set>

#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 9000000000000000000LL

#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 n;

ll tot, mn;

ll a[1000005], b[1000005];

bool mark[1000005];

void cal(ll x)

{

if(x == 1)return;

ll ans = 0;

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

b[i] = a[i];

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

{

ll t = b[i] % x;

if(t > abs(t - x))

t = t - x;

b[i + 1] += t;

ans += abs(t);

}

if(ans >= mn)

return;

mn = min(mn, ans);

}

int main()

{

mn = inf;

n = read();

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

{

a[i] = read();

tot += a[i];

}

if(tot == 1)

{

puts("-1");

return 0;

}

for(int i = 2; i <= sqrt(tot); i++)

if(tot % i == 0)

{

cal(i);

while(tot % i ==0)

tot /= i;

}

cal(tot);

cout << mn << endl;

return 0;

}

C. Point Ordering

难得见到计算几何题。把 1 看作原点，先找出 1 逆时针方向的下一个点，做法是先选一个弦，通过询问 2，不断找出弦逆时针方向的点 y，把 1，y 看作新的弦。

接下来以 1，y 为底边，询问以其它所有点为第三个顶点的三角形面积，逆时针看，这些三角形的面积是先递增后递减的。面积最大的那个三角形顶点向 1 连边，再次用询问 2，判断其它所有点在这个弦的哪个方向。分开这两部分的点后，各自按面积排序，就能找出所有的点顺序。

#include<map>
#include<set>
#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 9000000000000000000LL
#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 n;
ll s[1005];
vector<int>v1, v2;
bool cmp1(int x, int y)
{
    return s[x] < s[y];
}
bool cmp2(int x, int y)
{
    return s[x] > s[y];
}
int main()
{
    n = read();
    int x = 1, y = 2;
    for(int i = 3; i <= n; i++)
    {
        cout << 2 <<' '<< x <<' '<< y <<' '<< i <<endl;
        fflush(stdout);
        ll ans = read();
        if(ans < 0)
            y = i;
    }
    // cout << 'y' <<' '<< y << endl;
    int mx = 0;
    for(int i = 2; i <= n; i++)
        if(i != y)
        {
            cout << 1 <<' '<<x<<' '<<y<<' '<<i<<endl;
            fflush(stdout);
            s[i] = read();
            if(s[i] > s[mx])
                mx = i;
        }
    // cout << "mx" <<' '<< mx << endl;
    for(int i = 2; i <= n; i++)
        if(i != mx)
        {
            cout << 2 <<' '<<x<<' '<<mx<<' '<<i<<endl;
            fflush(stdout);
            ll ans = read();
            if(ans >= 0)
                v2.push_back(i);
            else v1.push_back(i);
        }
    cout << 0 <<' '<<1 <<' ';
    sort(v1.begin(), v1.end(), cmp1);
    sort(v2.begin(), v2.end(), cmp2);
    for(int i = 0; i < v1.size(); i++)
        cout << v1[i] <<' ';
    cout << mx <<' ';
    for(int i = 0; i < v2.size(); i++)
        cout << v2[i] <<' ';
    return 0;
}

#include<map>

#include<set>

#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 9000000000000000000LL

#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 n;

ll s[1005];

vector<int>v1, v2;

bool cmp1(int x, int y)

{

return s[x] < s[y];

}

bool cmp2(int x, int y)

{

return s[x] > s[y];

}

int main()

{

n = read();

int x = 1, y = 2;

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

{

cout << 2 <<' '<< x <<' '<< y <<' '<< i <<endl;

fflush(stdout);

ll ans = read();

if(ans < 0)

y = i;

}

// cout << 'y' <<' '<< y << endl;

int mx = 0;

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

if(i != y)

{

cout << 1 <<' '<<x<<' '<<y<<' '<<i<<endl;

fflush(stdout);

s[i] = read();

if(s[i] > s[mx])

mx = i;

}

// cout << "mx" <<' '<< mx << endl;

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

if(i != mx)

{

cout << 2 <<' '<<x<<' '<<mx<<' '<<i<<endl;

fflush(stdout);

ll ans = read();

if(ans >= 0)

v2.push_back(i);

else v1.push_back(i);

}

cout << 0 <<' '<<1 <<' ';

sort(v1.begin(), v1.end(), cmp1);

sort(v2.begin(), v2.end(), cmp2);

for(int i = 0; i < v1.size(); i++)

cout << v1[i] <<' ';

cout << mx <<' ';

for(int i = 0; i < v2.size(); i++)

cout << v2[i] <<' ';

return 0;

}

« 「CF1251X」Educational Codeforces Round 75 「CF1246X」Codeforces Round #596 (Div. 1) »

filament

竹取飞翔~~~~

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

「CF1254X」Codeforces Round #601 (Div. 1)

分类目录

热门文章

Myfriends

近期评论