《Codeforces Round #666 (Div. 2)》

A：签到题

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 105;
const int M = 5e4+5;
const LL Mod = 199999;
#define rg register
#define pi acos(-1)
#define INF 1e9
#define CT0 cin.tie(0),cout.tie(0)
#define IO ios::sync_with_stdio(false)
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
    void print(int x){
        if(x < 0){x = -x;putchar('-');}
        if(x > 9) print(x/10);
        putchar(x%10+'0');
    }
}
using namespace FASTIO;
void FRE(){
/*freopen("data1.in","r",stdin);
freopen("data1.out","w",stdout);*/}

string s[1005];
int cnt[30];
int main()
{
    int ca;ca = read();
    while(ca--)
    {
        memset(cnt,0,sizeof(cnt));
        int n;n = read();
        for(rg int i = 1;i <= n;++i) 
        {
            cin >> s[i];
            for(rg int j = 0;j < s[i].size();++j) cnt[s[i][j]-'a']++;
        }
        int f = 0;
        for(rg int j = 0;j < 26;++j) if(cnt[j]%n != 0) f = 1;
        printf("%s
",f ? "NO" : "YES");
    }
   // system("pause");
}

View Code

B：考虑枚举底数c。

那么这样复杂度是cn级别，显然不对。

但是仔细看可以发现，但c 稍微大一点，n稍微大一点，c^i就会超过1e18了。

然后对于选底数为1.最大花费也就1e5*1e9 = 1e14左右。

那么我们可以去枚举C，当某个点的单个花费都已经超过1e14了，那么肯定没有1的时候优，那么就退出。

可以发现，这样在c*n保持很小时就会结束了。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5+5;
const int M = 5e4+5;
const LL Mod = 199999;
#define rg register
#define pi acos(-1)
#define INF 1e18
#define CT0 cin.tie(0),cout.tie(0)
#define IO ios::sync_with_stdio(false)
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
    void print(int x){
        if(x < 0){x = -x;putchar('-');}
        if(x > 9) print(x/10);
        putchar(x%10+'0');
    }
}
using namespace FASTIO;
void FRE(){
/*freopen("data1.in","r",stdin);
freopen("data1.out","w",stdout);*/}

LL a[N],b[N],ans = INF;
int main()
{
    int n;n = read();
    for(rg int i = 1;i <= n;++i) a[i] = read();
    sort(a+1,a+n+1);
    int f = 0;
    for(rg int low = 1;;low++)
    {
        LL ma = 1;
        b[1] = 1;
        for(rg int i = 2;i <= n;++i) 
        {
            ma *= low;
            b[i] = ma;
            if(ma > 1e15){f = 1;break;}
        }
        if(f) break;
        LL tmp = 0;
        for(rg int i = 1;i <= n;++i) tmp += abs(a[i]-b[i]);
        ans = min(ans,tmp);
    }
    printf("%lld
",ans);
    //system("pause");
}

View Code

C：考虑一种思路。

对于前n-1个数，加上(n-1)*a[i]。

那么次数第i个位置的数肯定是n*a[i]。

那么满足时n的倍数，可以直接-n*a[i]，然后我们再让a[n]加上n*a[n]-a[n]即可。

然后最后都减去他们自身即可满足三次。注意特判n = 1的情况

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5+5;
const int M = 1e6+5;
const LL Mod = 199999;
#define rg register
#define pi acos(-1)
#define INF 1e18
#define CT0 cin.tie(0),cout.tie(0)
#define IO ios::sync_with_stdio(false)
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
    void print(int x){
        if(x < 0){x = -x;putchar('-');}
        if(x > 9) print(x/10);
        putchar(x%10+'0');
    }
}
using namespace FASTIO;
void FRE(){
/*freopen("data1.in","r",stdin);
freopen("data1.out","w",stdout);*/}

LL b[N],a[N];
int main()
{
    int n;n = read();
    for(rg int i = 1;i <= n;++i) a[i] = read();
    if(n == 1)
    {
        printf("1 1
");
        printf("1
");
        printf("1 1
");
        printf("1
");
        printf("1 1
");
        printf("%d
",-a[1]-2);
    }
    else
    {
        for(rg int i = 1;i < n;++i) b[i] = 1LL*(n-1)*a[i],a[i] += b[i];
        printf("1 %d
",n-1);
        for(rg int i = 1;i < n;++i) printf("%lld%c",b[i],i == n-1 ? '
' : ' ');
        printf("%d %d
",n,n);
        printf("%lld
",1LL*n*a[n]-a[n]);
        a[n] = 1LL*n*a[n];
        printf("%d %d
",1,n);
        for(rg int i = 1;i <= n;++i) printf("%lld%c",-a[i],i == n ? '
' : ' ');
    }
   // system("pause");
}

View Code

D：博弈论

暴力解法：肯定选更大的好，那么模拟一下选的过程即可

可以发现，当某个堆的数都大于其他堆的和时。

先手选这个堆必胜。

当不满足时，最后肯定会选到剩下1.那么判断下所有堆的和的奇偶性即可。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5+5;
const int M = 1e6+5;
const LL Mod = 199999;
#define rg register
#define pi acos(-1)
#define INF 1e18
#define CT0 cin.tie(0),cout.tie(0)
#define IO ios::sync_with_stdio(false)
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
    void print(int x){
        if(x < 0){x = -x;putchar('-');}
        if(x > 9) print(x/10);
        putchar(x%10+'0');
    }
}
using namespace FASTIO;
void FRE(){
/*freopen("data1.in","r",stdin);
freopen("data1.out","w",stdout);*/}

int a[105];
int main()
{
    int ca;ca = read();
    while(ca--)
    {
        int mx = -1,sum = 0;
        int n;n = read();
        for(rg int i = 1;i <= n;++i) a[i] = read(),sum += a[i],mx = max(mx,a[i]);
        if(mx > sum-mx) printf("T
");
        else
        {
            if(sum&1) printf("T
");
            else printf("HL
");
        }
    }
   // system("pause");
}

View Code