A - Too Rich

给定每一种面值的硬币的个数，求出用最多硬币表示出所给价值。

倒着做可以用前缀和优化和剪枝。

可以$O(1)$算出当前面值减去前缀和之后最少需要几个，然后在此基础上多做3次就可以了，因为前一种硬币最多3枚就可以表示后一种硬币了。

#include 
    
     using namespace std;typedef long long ll;const int dx[] = {1, 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 2000};int a[20];int T, p;ll S[20];int ans;inline void upd(int &x, int y) {    if (y > x) x = y;}void dfs(int dep, ll val, int coins) {    //printf("%d %d %d\n", dep, val, coins);    if (val < 0) {        return;    }    if (val == 0) {        upd(ans, coins);        return;    }    if (dep == 0) {        return;    }    int left = val - S[dep - 1];    if (left <= 0) {        dfs(dep - 1, val, coins);        if (a[dep] >= 1)            dfs(dep - 1, val - dx[dep], coins + 1);    } else {        int i = left / dx[dep];        if (left % dx[dep]) i++;        if (i <= a[dep])            dfs(dep - 1, val - i * dx[dep], coins + i);        else            dfs(dep - 1, val - a[dep]*dx[dep], coins + i);        i++;        if (i <= a[dep])            dfs(dep - 1, val - i * dx[dep], coins + i);        i++;        if (i <= a[dep])            dfs(dep - 1, val - i * dx[dep], coins + i);    }}int main() {    scanf("%d", &T);    while (T--) {        scanf("%d", &p);        for (int i = 1; i <= 10; i++)            scanf("%d", &a[i]);        for (int i = 1; i <= 10; i++)            S[i] = S[i - 1] + (ll)(a[i] * dx[i]);        ans = -1;        dfs(10, (ll)p, 0);        cout << ans << endl;    }    return 0;}
    

B - Count a * b

猜了一发结论$\sum_{i|n} i^2 - \sum_{i|n} 1$，结果是tle，卡了$O(T\sqrt(n))$的做法，加了枚举的优化。

#include 
    
     using namespace std;typedef long long ll;typedef unsigned long long ull;const int N = 1e5;bool p[100005];int prime[100005],top;struct node{    int x,y;}ort[10005];void init(){    memset(p, 0, sizeof(p));    top = 0;    for (int i = 2; i <= N; ++i) {        if (!p[i]) {            prime[++top] = i;        }        for (int j = 1; j <= top; ++j) {            if (i * prime[j] > N)                break;            p[i * prime[j]] = 1;            if (i % prime[j] == 0)                break;        }    }}ull r1,r2;int ctop;void dfs(int dep,int now){    if(dep==ctop+1){        r1+=(ull)now*now;        return;    }    int t=1;    for(int i=0;i<=ort[dep].y;i++){        dfs(dep+1,now*t);        t*=ort[dep].x;    }}int main() {    //freopen("in.txt","r",stdin);    init();    int n, T;    cin >> T;    while (T--) {        scanf("%d", &n);        int tmp=n;        // ull res1 = 0, res2 = 0;        // for (int i = 1; i * i <= n; i++) {        //  if (n % i == 0) {        //      res1 += (ull)i * i;        //      res2 ++;        //      if (i * i != n) {        //          int t = n / i;        //          res1 += (ull)t * t;        //          res2 ++;        //      }        //  }        // }        // res1 -= (ull)n * res2;        // printf("%llu\n", res1);        ctop=0;        for(int i=1;i<=top && prime[i]*prime[i]<=n;i++){            if(n%prime[i]==0){                ctop++;                ort[ctop].x=prime[i];                ort[ctop].y=0;                while(n%prime[i]==0){                    ort[ctop].y++;                    n/=prime[i];                }            }        }        if(n!=1){            ctop++;            ort[ctop].x=n;            ort[ctop].y=1;        }        r1=0;r2=1;        for(int i=1;i<=ctop;i++)            r2=r2*(ull)(ort[i].y+1);        r2=r2*(ull)tmp;        dfs(1,1);        cout<
     
      <
     
    

F - Almost Sorted Array

判断是不是almost sorted array。

跟着跑LIS，如果栈高比当前i小太多直接就是不对的了。

所以复杂度还是$O(n)$。

#include 
    
     using namespace std;const int maxn = 1e5 + 5;int T, n, k, a[maxn], k1, k2, ans[maxn], len, b[maxn], flag;template
     
       inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}template
      
        inline void read(A&x,B&y){read(x);read(y);}template
       
         inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}template
        
          inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}int main() {    //freopen("in.txt", "r", stdin);    read(T);    while (T--) {        flag = 0;        memset(ans, 0, sizeof(ans));        k1 = k2 = 0;        scanf("%d", &n);        for (int i = 1; i <= n; i++)            read(a[i]);        ans[1] = a[1];        len = 1;        for (int i = 2; i <= n; i++) {            if (a[i] >= ans[len])                ans[++len] = a[i];            else {                int pos = upper_bound(ans + 1, ans + len + 1, a[i]) - ans;                ans[pos] = a[i];            }            if(i-len>5) break;        }        if (len >= n - 1) {            puts("YES");            continue;        }        for (int i = 1; i <= n; i++)            b[i] = a[n - i + 1];        ans[1] = b[1];        len = 1;        for (int i = 2; i <= n; i++) {            if (b[i] >= ans[len])                ans[++len] = b[i];            else {                int pos = upper_bound(ans + 1, ans + len + 1, b[i]) - ans;                ans[pos] = b[i];            }            if(i-len>5) break;        }        if (len >= n - 1) puts("YES");        else puts("NO");    }    return 0;}
        
       
      
     
    

G - Dancing Stars on Me

每个点只有两个最近点，并且最近的距离相等。

#include 
    
     using namespace std;typedef long long ll;double eps = 1e-8;inline int dcmp(double x) {    if (x > eps) return 1;    if (x < -eps) return -1;    return 0;}struct node {    int x, y;} info[1005];int cnt[1005];double getdist(int i, int j) {    double rx = info[i].x - info[j].x;    double ry = info[i].y - info[j].y;    double ret = rx * rx + ry * ry;    return ret;}int main() {    //freopen("in.txt","r",stdin);    int T,n;    cin >> T;    while (T--) {        scanf("%d", &n);        for (int i = 1; i <= n; i++)            scanf("%d%d", &info[i].x, &info[i].y);        double cmp = 1e15;        for (int i = 2; i <= n; i++) {            cmp = min(cmp, getdist(1, i));        }        bool flag=1;        memset(cnt,0,sizeof cnt);        for(int i=1;i<=n;i++){            for(int j=1;j<=n;j++){                if(i==j) continue;                if(dcmp(getdist(i,j)-cmp)==0) cnt[i]++;                if(dcmp(getdist(i,j)-cmp)<0){                    flag=0;                    break;                }            }        }        for(int i=1;i<=n;i++)            if(cnt[i]!=2){                flag=0;                break;            }        puts(flag?"YES":"NO");    }    return 0;}
    

H - Partial Tree

2n-2个度分配给n个点。

原本是一个二维消费的背包。

有一个特殊的条件就是每个点至少一个度，那么可以直接先把这些度分配给n个点。

然后就是n-2个度任意分配的背包问题，把得到的价值修改成a[i+1]-a[1]就行了。

#include 
    
     using namespace std;typedef long long ll;int f[10005];int dp[4400],res;int main() {    //freopen("in.txt","r",stdin);    int T,n;    cin >> T;    while (T--) {        scanf("%d",&n);        for(int i=1;i
    

J - Chip Factory

居然可以暴力过。

#include 
    
     using namespace std;typedef long long ll;template
     
       inline void read(T &x) {    x = 0; T f = 1; char ch; do {ch = getchar(); if (ch == '-')f = -1;} while (ch < '0' || ch > '9'); do x = x * 10 + ch - '0', ch = getchar(); while (ch <= '9' && ch >= '0'); x *= f;}template
      
        inline void read(A&x, B&y) {read(x); read(y);}template
       
         inline void read(A&x, B&y, C&z) {read(x); read(y); read(z);}template
        
          inline void read(A&x, B&y, C&z, D&w) {read(x); read(y); read(z); read(w);}int a[1005];int main() {    //freopen("in.txt","r",stdin);    int T, n;    read(T);    while (T--) {        read(n);        for (int i = 1; i <= n; i++)            read(a[i]);        int Mx = 0;        for (int i = 1; i < n; i++)            for (int j = i + 1; j < n; j++)                for (int k = j + 1; k <= n; k++) {                    Mx = max(Mx, (a[i] + a[j])^a[k]);                    Mx = max(Mx, (a[i] + a[k])^a[j]);                    Mx = max(Mx, (a[k] + a[j])^a[i]);                }        printf("%d\n",Mx);    }    return 0;}
        
       
      
     
    

然后$O(n^2 log n)$，枚举$S_i$,$S_j$从字典树删除,贪心查询$S_k$。

#include 
    
     using namespace std;const int maxn = 10000+5;typedef long long ll;ll bin[35];int n,m;ll a[maxn],x;template
     
       inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}template
      
        inline void read(A&x,B&y){read(x);read(y);}template
       
         inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}template
        
          inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}struct trie{    int cnt;    int ch[maxn*35][2];    ll val[maxn*35];    int ts[maxn*35];    inline void init(){        cnt=1;        memset(ch[0],0,sizeof ch[0]);        ts[0]=0;        //memset(ts,0,sizeof ts);    }    inline void insert(ll a){        int u=0;        for(int i=32;i>=0;i--){            ll t=a&bin[i];t>>=i;            if(!ch[u][t]){                memset(ch[cnt],0,sizeof ch[cnt]);                val[cnt]=0;                ts[cnt]=0;                ch[u][t]=cnt++;            }            u=ch[u][t];            ts[u]++;        }        val[u]=a;    }    inline void del(ll a){        int u=0;        for(int i=32;i>=0;i--){            ll t=a&bin[i];t>>=i;            u=ch[u][t];            ts[u]--;        }    }    inline ll query(ll a){        int u=0;        for(int i=32;i>=0;i--){            ll t=a&bin[i];t>>=i;            if(ch[u][t^1]&&ts[ch[u][t^1]]) u=ch[u][t^1];            else u=ch[u][t];        }        return val[u]^a;    }}Trie;int main(){    //freopen("in.txt","r",stdin);    bin[0]=1;for(ll i=1;i<=35;i++) bin[i]=bin[i-1]*2ll;    int T,cas=1;    for(cin>>T,cas=1;cas<=T;cas++){        scanf("%d",&n);        Trie.init();        for(int i=1;i<=n;i++){            read(a[i]);            Trie.insert(a[i]);        }        ll mx=0;        for(int i=1;i<=n;i++)            for(int j=i+1;j<=n;j++){                Trie.del(a[i]);Trie.del(a[j]);                mx=max(mx,Trie.query(a[i]+a[j]));                Trie.insert(a[i]);Trie.insert(a[j]);            }        printf("%lld\n",mx);    }    return 0;}
        
       
      
     
    

L - House Building

#include 
    
     #define rep(i,x,y) for(int i=x;i<=y;i++)#define per(i,x,y) for(int i=x;i>=y;i--)#define debug(a) cerr<<#a<<"=="<
     <