Educational Codeforces Round 84

A. Sum of Odd Integers

for i in range (int(input())):
    n,k=map(int,input().split())
    if k*k<=n and (n-k*k)%2==0:
        print("YES")
    else:
        print("NO")

B. Princesses and Princes

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int main(){
   // IN
    int t;cin>>t;
    while(t--){
        int n;sc("%d",&n);
        vector<int>g[n+1],girl(n+1,0),boy(n+1,0);
        for(int i=1;i<=n;i++){
            int k;sc("%d",&k);
            for(int j=0;j<k;j++){
                int kd;sc("%d",&kd);
                g[i].push_back(kd);
            }
        }
        for(int i=1;i<=n;i++){
            for(int j:g[i]){
                if(!boy[j]){
                    girl[i]=1;
                    boy[j]=1;
                    break;
                }
            }
        }
        int x=-1,y=-1;
        for(int i=1;i<=n;i++){
            if(!girl[i])x=i;
            if(!boy[i])y=i;
        }
        if(x!=-1&&y!=-1){
            O("IMPROVE");
            cout<<x<<" "<<y<<endl;
        }else O("OPTIMAL");
    }
}

C. Game with Chips

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,m,k;
int main(){
    //IN
    cin>>n>>m>>k;
    for(int i=0;i++<2*k;sc("%*d%*d"));
    if(n==1&&m==1)return O(0);
    string ans="";
    for(int i=0;i<n-1;i++)ans+="U";
    for(int j=0;j<m-1;j++)ans+="L";
    for(int i=0;i<n;i++){
        for(int j=0;j<m-1;j++){
            if(i&1)ans+="L";
            else ans+="R";
        }
        if(i<n-1)ans+="D";
    }
    O(ans.length());O(ans);
}

D. Infinite Path

先处理出环，对于长度为 $L$ 的环，要找到最小的 $K$ ，暴力是不可能的，
我们要找到一些位置 $P$ ，枚举 $P+x*K$ 的位置。
有个结论是在环中走 $K$ 步，最小步长是 $gcd(K,L)$ 。
所以枚举 $L$ 因子即可。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n;
int p[N],c[N],vis[N];
int main(){
    int t;cin>>t;
    while(t--){
        sc("%d",&n);int ans=N;
        for(int i=0;i++<n;sc("%d",&p[i]));
        for(int i=0;i++<n;sc("%d",&c[i]));
        for(int i=0;i++<n;vis[i]=0);
        for(int i=1;i<=n;i++){
            if(vis[i])continue;
            vector<int>v;
            for(int j=i;!vis[j];j=p[j])v.push_back(j),vis[j]=1;
            int m=v.size();
            function<bool(int pt)>fun=[&](int pt){
                for(int I=0;I<pt;I++){
                    bool f=1;
                    for(int J=I+pt;J<m&&f;J+=pt)
                    if(c[v[J]]!=c[v[J-pt]])f=0;
                    if(f)return 1;
                }
                return 0;
            };
            for(int j=1;j*j<=m;j++){
                if(m%j==0){
                    if(j<ans&&fun(j))ans=j;
                    if(j*j!=m&&m/j<ans&&fun(m/j))ans=m/j;
                }
            }
        }
        pr("%d\n",ans);
    }
}

E. Count The Blocks

简单数学，推下公式即可。 $ans=18\cdot 10^{x-1}+81\cdot (x-2)\cdot 10^{x-2}$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=998244353;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
template <int M>struct ModInt
{
    using lint = long long;
    static int get_M() { return M; }
    static int get_primitive_root() {
        static int primitive_root = 0;
        if (!primitive_root) {
            primitive_root = [&](){
                std::set<int> fac;
                int v = M - 1;
                for (lint i = 2; i * i <= v; i++) while (v % i == 0) fac.insert(i), v /= i;
                if (v > 1) fac.insert(v);
                for (int g = 1; g < M; g++) {
                    bool ok = true;
                    for (auto i : fac) if (ModInt(g).power((M - 1) / i) == 1) { ok = false; break; }
                    if (ok) return g;
                }
                return -1;
            }();
        }
        return primitive_root;
    }
    int val;
    constexpr ModInt() : val(0) {}
    constexpr ModInt &_setval(lint v) { val = (v >= M ? v - M : v); return *this; }
    constexpr ModInt(lint v) { _setval(v % M + M); }
    explicit operator bool() const { return val != 0; }
    constexpr ModInt operator+(const ModInt &x) const { return ModInt()._setval((lint)val + x.val); }
    constexpr ModInt operator-(const ModInt &x) const { return ModInt()._setval((lint)val - x.val + M); }
    constexpr ModInt operator*(const ModInt &x) const { return ModInt()._setval((lint)val * x.val % M); }
    constexpr ModInt operator/(const ModInt &x) const { return ModInt()._setval((lint)val * x.inv() % M); }
    constexpr ModInt operator-() const { return ModInt()._setval(M - val); }
    constexpr ModInt &operator+=(const ModInt &x) { return *this = *this + x; }
    constexpr ModInt &operator-=(const ModInt &x) { return *this = *this - x; }
    constexpr ModInt &operator*=(const ModInt &x) { return *this = *this * x; }
    constexpr ModInt &operator/=(const ModInt &x) { return *this = *this / x; }
    friend constexpr ModInt operator+(lint a, const ModInt &x) { return ModInt()._setval(a % M + x.val); }
    friend constexpr ModInt operator-(lint a, const ModInt &x) { return ModInt()._setval(a % M - x.val + M); }
    friend constexpr ModInt operator*(lint a, const ModInt &x) { return ModInt()._setval(a % M * x.val % M); }
    friend constexpr ModInt operator/(lint a, const ModInt &x) { return ModInt()._setval(a % M * x.inv() % M); }
    constexpr bool operator==(const ModInt &x) const { return val == x.val; }
    constexpr bool operator!=(const ModInt &x) const { return val != x.val; }
    bool operator<(const ModInt &x) const { return val < x.val; }  // To use std::map<ModInt, T>
    friend std::istream &operator>>(std::istream &is, ModInt &x) { lint t; is >> t; x = ModInt(t); return is; }
    friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { os << x.val;  return os; }
    constexpr lint power(lint n) const {
        lint ans = 1, tmp = this->val;
        while (n) {
            if (n & 1) ans = ans * tmp % M;
            tmp = tmp * tmp % M;
            n >>= 1;
        }
        return ans;
    }
    constexpr lint inv() const { return this->power(M - 2); }
    constexpr ModInt operator^(lint n) const { return ModInt(this->power(n)); }
    constexpr ModInt &operator^=(lint n) { return *this = *this ^ n; }

    inline ModInt fac() const {
        static std::vector<ModInt> facs;
        int l0 = facs.size();
        if (l0 > this->val) return facs[this->val];
        facs.resize(this->val + 1);
        for (int i = l0; i <= this->val; i++) facs[i] = (i == 0 ? ModInt(1) : facs[i - 1] * ModInt(i));
        return facs[this->val];
    }

    ModInt doublefac() const {
        lint k = (this->val + 1) / 2;
        if (this->val & 1) return ModInt(k * 2).fac() / ModInt(2).power(k) / ModInt(k).fac();
        else return ModInt(k).fac() * ModInt(2).power(k);
    }

    ModInt nCr(const ModInt &r) const {
        if (this->val < r.val) return ModInt(0);
        return this->fac() / ((*this - r).fac() * r.fac());
    }

    ModInt sqrt() const {
        if (val == 0) return 0;
        if (M == 2) return val;
        if (power((M - 1) / 2) != 1) return 0;
        ModInt b = 1;
        while (b.power((M - 1) / 2) == 1) b += 1;
        int e = 0, m = M - 1;
        while (m % 2 == 0) m >>= 1, e++;
        ModInt x = power((m - 1) / 2), y = (*this) * x * x;
        x *= (*this);
        ModInt z = b.power(m);
        while (y != 1) {
            int j = 0;
            ModInt t = y;
            while (t != 1) j++, t *= t;
            z = z.power(1LL << (e - j - 1));
            x *= z, z *= z, y *= z;
            e = j;
        }
        return ModInt(std::min(x.val, M - x.val));
    }
};
using mint =ModInt<mod>;
int main(){
    int n;cin>>n;
    for(int i=1;i<n;i++){
        mint y=10,x=n-i-1;
        y^=n-i-1;
        mint ans=y*(x*81+180);
        cout<<ans<<' ';
    }
    O(10);
}