Codeforces Round #589 (Div. 2)【数学 + 构造】

A题 Distinct Digits

  因为数的大小最长也就是5位，所以直接暴力求解即可，复杂度O(5 * N)。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&( -x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define efs 1e-7
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
int x, y;
bool check(int val)
{
    bool vis[10] = {false};
    int tmp;
    while(val)
    {
        tmp = val % 10;
        if(vis[tmp]) return false;
        vis[tmp] = true;
        val /= 10;
    }
    return true;
}
int main()
{
    scanf("%d%d", &x, &y);
    for(int i=x; i<=y; i++)
    {
        if(check(i))
        {
            printf("%d\n", i);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

B题 Filling the Grid

  直接判断哪些格子被固定了，需要判断哪些格子置黑与强制为白的冲突性，因为那会决定答案的存在性。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&( -x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define efs 1e-7
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e3 + 7;
const ll mod = 1e9 + 7;
int vis[maxN][maxN] = {0};
int N, M;
ll jc[maxN * maxN];
inline ll fast_mi(ll a, int b)
{
    ll ans = 1LL;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll solve(int val)
{
    ll ans = 0;
    for(int i=0; i<=val; i++)
    {
        ans = (ans + jc[val] * fast_mi(jc[i], mod - 2) % mod * fast_mi(jc[val - i], mod - 2) % mod) % mod;
    }
    return ans;
}
int main()
{
    jc[0] = jc[1] = 1;
    for(int i=2; i<=1e6; i++) jc[i] = jc[i-1] * i % mod;
    scanf("%d%d", &N, &M);
    for(int i=1, r, j; i<=N; i++)
    {
        scanf("%d", &r);
        for(j=1; j<=r; j++) vis[i][j] = 1;
        vis[i][j] = -1;
    }
    bool flag = true;
    for(int i=1, w, j; i<=M; i++)
    {
        scanf("%d", &w);
        for(j=1; j<=w; j++)
        {
            if(vis[j][i] == -1) flag = false;
            vis[j][i] = 1;
        }
        if(vis[j][i] == 1) flag = false;
        vis[j][i] = -1;
    }
//    for(int i=1; i<=N; i++)
//    {
//        for(int j=1; j<=M; j++)
//        {
//            printf("%d ", vis[i][j]);
//        }
//        printf("\n");
//    }
    if(!flag)
    {
        printf("0\n");
        return 0;
    }
    int sum = 0;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) sum += (vis[i][j] ? 0 : 1);
    printf("%lld\n", solve(sum));
    return 0;
}

C题 Primes and Multiplication

  直接求质数对原数产生的贡献即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&( -x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define efs 1e-7
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e6 + 7;
const ll mod = 1e9 + 7;
bool Prime[maxN] = {false};
int inque[maxN], cnt = 0;
ll X, N;
vector<ll> vt;
inline ll fast_mi(ll a, ll b)
{
    ll ans = 1LL;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
inline void pre_did()
{
    for(int i=2; i<=1e6; i++)
    {
        if(!Prime[i])
        {
            inque[++cnt] = i;
            for(int j = 2 * i; j <= 1e6; j += i) Prime[j] = true;
        }
    }
}
int main()
{
    pre_did();
    scanf("%lld%lld", &X, &N);
    for(int i=1; i<=cnt; i++)
    {
        if(X % inque[i] == 0)
        {
            vt.push_back(inque[i]);
            while(X % inque[i] == 0) X /= inque[i];
        }
    }
    if(X ^ 1) vt.push_back(X);
    int len = (int)vt.size();
    ll tmp1, tmp2, cop, ans = 1LL;
    for(int i=0; i<len; i++)
    {
        tmp1 = tmp2 = 0;
        cop = N;
        while(cop)
        {
            tmp1 = cop / vt[i];
            cop /= vt[i];
            tmp2 += tmp1;
        }
        ll _get = fast_mi(vt[i], tmp2);
        ans = ans * _get % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

D题 Complete Tripartite

  开虚拟的时候唯独没有想全的题了，具体思维。

  首先，我们不是所有的边都是需要的，尤其是我们指向下一个节点的时候，我们可以小的结点去指向大的结点，并且固定如此，让一开始所有的结点都在集合1中，然后呢，我们从1号结点开始进行处理，所有的有链接的且在同一个集合中的点，我们对于序号大的点放进一个更大的集合中去，保证了题目中的所要的要求了。

  但是，我们尽管这样做了之后，可以保证每个集合内的点是互相之间没有边链接的，但是呢（亲测，WA10），我们现在还是没有保证集合中的各点到除了自己之外的集合中的各点都有一条边链接。

  这样，我们还要处理第二条规则，首先可以看到，两个点之所以不在一个集合，是因为他们之间是有边相连接的，所以在这里，利用这条规则，我们只需要去判断一下，1号集合与2号集合的总的边的数量、1号集合与3号集合的总的边的数量、2号集合与3号集合的总的边的数量的总和是不是等于M即可。等于M，表示了每条边都用上了，保证了题目中的要求。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&( -x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define efs 1e-7
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, M, team[maxN] = {0}, head[maxN], cnt, tot, op[4] = {0};
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[600007];
inline void addEddge(int u, int v)
{
    if(u > v) return;
    edge[cnt] = Eddge(head[u], v);
    head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
inline void init()
{
    cnt = 0; tot = 1;
    for(int i=1; i<=N; i++) head[i] = -1;
    for(int i=1; i<=N; i++) team[i] = 1;
}
int main()
{
    scanf("%d%d", &N, &M);
    init();
    for(int i=1, u, v; i<=M; i++)
    {
        scanf("%d%d", &u, &v);
        _add(u, v);
    }
    for(int u=1; u<=N; u++)
    {
        for(int i=head[u], v; ~i; i=edge[i].nex)
        {
            v = edge[i].to;
            if(team[v] == team[u]) team[v]++;
            tot = max(tot, team[v]);
        }
    }
    if(tot == 3)
    {
        for(int i=1; i<=N; i++) op[team[i]]++;
        if((op[1] * op[2] + op[1] * op[3] + op[2] * op[3]) ^ M) { printf("-1\n"); return 0; }
        for(int i=1; i<=N; i++) printf("%d ", team[i]);
        printf("\n");
    }
    else printf("-1\n");
    return 0;
}