CodeCraft-21 and Codeforces Round #711 (Div. 2)

A. GCD Sum

思路：
虽然，当个位是偶数，然后总体只有奇数个奇数时，一定是大于1的

MyCode：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,maxm=2e5+10,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
inline void solve() {
    ll n;
    cin>>n;
    for(ll x=n,y,sum;; ++x) {
        sum=0;
        y=x;
        while(y) {
            sum+=y%10;
            y/=10;
        }
        if(__gcd(x,sum)>1) {
            cout<<x<<'\n';
            return;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B. Box Fitting

思路：
考虑先放入大的，再放小的。
那么可以写个的暴力，但是因为物块的宽度是2的次幂，所以暴力的复杂度只要

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,maxm=2e5+10,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int a[21],pw[21];
inline void solve() {
    int n,w,ans(0);
    cin>>n>>w;
    for(int i=1,x;i<=n;++i) {
        cin>>x;
        a[(int)log2(x)]+=1;
    }
    ll sum=w;
    while(n) {
        ans+=1;
        for(int i=19;~i;--i) while(a[i]&&pw[i]<=sum) {
            a[i]-=1;
            n-=1;
            sum-=pw[i];
        }
        sum=w;
    }
    cout<<ans<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    pw[0]=1;
    for(int i=1;i<=20;++i) pw[i]=pw[i-1]<<1;
    int T;    
    cin>>T;
    while(T--) solve();
    return 0;
}

C. Planar Reflections

看完题目就不用多想了，满足递归的性质，爆搜+记忆化去模拟
爆搜除了要注意记忆化搜索，还要避免多次访问同一个状态

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,maxm=2e5+10,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int n,k;
ll dp[1003][1003];
ll dfs(int i,int j) {
    if(~dp[i][j]) return dp[i][j];
    if(j==1||!i) return dp[i][j]=1;
    ll ans(0);
    return dp[i][j]=(dfs(k-i,j-1)+dfs(i-1,j))%mod;
}
inline void solve() {
    cin>>k>>n;
    memset(dp,-1,sizeof dp);
    cout<<dfs(k,n)<<'\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;    
    cin>>T;
    while(T--) solve();
    return 0;
}

D. Bananas in a Microwave

输出每个数最早可以得到的回合，反之输出-1

思路：
就和筛一样的思路，假如第i回合是加法，表示当前是第i个回合j的状态，如果，那么要么在之前就得到了，要么在这个回合可以得到。乘法同理。
结果其实和第一维没有联系，可以滚动掉。
向上取整，尤其是乘法向上取整的处理

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5,maxm=2e5+10,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,op,y;
    ll x;
    cin>>n>>m;
    vector<int>a(m+1,-1);
    a[0]=0;
    for(int i=1;i<=n;++i) {
        cin>>op>>x>>y;
        if(op&1) {
            x=(x+maxn-1)/maxn;
            for(int j=m;~j;--j) if(~a[j]) {
                for(int t=1,k=x+j;t<=y&&k<=m&&a[k]==-1;++t,k+=x) a[k]=i; 
            }
        }
        else {
            for(int j=m;~j;--j) if(~a[j]) {
                ll k=(x*j+maxn-1)/maxn;
                for(int t=1;t<=y&&k<=m&&a[k]==-1;++t,k=(x*k+maxn-1)/maxn) a[k]=i; 
            }
        }
    }
    for(int i=1;i<=m;++i) cout << a[i] << " \n"[i == m];
    return 0;
}

E. Two Houses

大佬理解的意思：

从距离最大的两点开始问起。如果入度大的点都能到入度小的点，很容易构造出入度小的点到入度大的点的路径。
MyCode：

#include <bits/stdc++.h>
using namespace std;
const int maxn=507,maxm=2e5+10,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
inline void solve() {
    int n;
    cin >> n;
    int ar[n+1];
    for(int i=1;i<=n;i++) cin >> ar[i];
    vector<tuple<int,int,int> > edge;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(ar[i] > ar[j]) edge.emplace_back(ar[i]-ar[j],i,j);
            else edge.emplace_back(ar[j]-ar[i],j,i);
        }
    }
    sort(edge.rbegin(),edge.rend());
    for(auto it : edge){
        cout << "? " << get<1>(it) << " " << get<2>(it) << endl;
        string s;
        cin >> s;
        if(s == "Yes"){
            cout << "! " << get<1>(it) << " " << get<2>(it) << endl;
            return;
        }
    }
    cout << "! 0 0" << endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;    
    T=1;    
//    cin>>T;
    while(T--) solve();
    return 0;
}