2019 Multi-University Training Contest 4

Solved	Pro.ID	Title	Ratio(Accepted / Submitted)
	1001	AND Minimum Spanning Tree	31.75%(1018/3206)
	1002	Colored Tree	0.00%(0/105)
	1003	Divide the Stones	10.35%(126/1217)
	1004	Enveloping Convex	0.00%(0/125)
	1005	Good Numbers	17.65%(9/51)
	1006	Horse	29.03%(18/62)
	1007	Just an Old Puzzle	31.83%(875/2749)
	1008	K-th Closest Distance	10.97%(376/3429)
	1009	Linear Functions	0.00%(0/35)
已补	1010	Minimal Power of Prime	6.15%(328/5331)

1001

偶数点和1连，奇数点找二进制表示下的第一个为0的位置，使该位为1的二进制数，若比n大，则该奇数与1配对，否则与该数配对

#include <bits/stdc++.h>
using namespace std;
int ans[200005];
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        int anss = 0;
        for(int i = 2; i <= n; i++) {
            if(i % 2 == 0) ans[i] = 1;
            else {
                int tmp = i;
                int cnt = 0;
                bool f = false;
                while(tmp) {
                    if(tmp & 1) cnt++;
                    else {
                        f = true;
                        break;
                    }
                    tmp >>= 1;
                }
                if(f) ans[i] = 1 << cnt;
                else {
                    if((1 << cnt) <= n) ans[i] = 1 << cnt;
                    else ans[i] = 1, anss++;
                }
            }
        }
        printf("%d\n", anss);
        for(int i = 2; i <= n; i++) {
            if(i != n) printf("%d ", ans[i]);
            else printf("%d\n", ans[i]);
        }
    }
    return 0;
}

1007

看结果与初始状态的序列的逆序对个数差和0所在行的位置差的奇偶关系是否一致。

#include <bits/stdc++.h>
using namespace std;
int a[7][7];
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int ans = 0;
        for(int i = 1; i <= 4; i++) {
            for(int j = 1; j <= 4; j++) {
                scanf("%d", &a[i][j]);
                if(a[i][j] == 0) ans += 4 - i;
            }
        }
        ans %= 2;
        int res = 0;
        for(int i = 1; i <= 4; i++) {
            for(int j = 1; j <= 4; j++) {
                if(a[i][j] == 0)continue;
                for(int k1 = i; k1 <= 4; k1++) {
                    int t;
                    if(k1 == i) t = j + 1;
                    else t = 1;
                    for(int k2 = t; k2 <= 4; k2++) {
                        if(a[k1][k2] == 0) continue;
                        if(a[i][j] > a[k1][k2]) res++;
                    }
                }
            }
        }
        res %= 2;
        if((res == 1 && ans == 1)||(res == 0 && ans == 0)){
            puts("Yes");
        }
        else{
            puts("No");
        }
    }
    return 0;
}

1010

x最大1e18，观察分解后的质因数，可以先遍历比较小的质因子，那么剩下的就不会太大了，比如1000附近的质数，指数为6就1e18了，所以当我们把小于1200（或1100）的质数全部考虑了之后，剩下的那个数字可能是\(p^1\)、\(p^2\) 、\(p_1^2p_2^2\)、\(p^3\) 、\(p^4\) 、\(p^5\) 、\(p_1^3p_2^2\)发现并不好判断最小质数。所以我们把这个情况扩大到指数为5的情况，把\(x^{1\over 5}\)的质因数分解掉，然后剩下的部分只可能是\(p^1\) 、\(p^2\) 、\(p^3\) 、\(p^2p_2^2\) 、\(p^4\)

所以只需要做开方运算然后再乘方判断是否相等就好了

标答：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1500;
int p[N],v[N],tot;
void getP(){
    for(int i=2;i<N;i++){
        if(!v[i])p[++tot] = i;
        for(int j=1;j<=tot && p[j] * i < N;j++){
            v[p[j] * i] = 1;
            if(i % p[j] == 0)break;
        }
    }
}
inline ll po(ll a,int b){
  ll ret=1;
  while(b--)ret*=a;
  return ret;
}
inline bool ok(ll x,int k){
    int t = round(pow(x,1.0/k));
    if(po(t,k) == x)return true;
    else return false;
}
inline int solve(ll x){
    int res = 100;
    for(int i=1;i<=tot && p[i] <= x ;i++){
        int z = 0;
        while(x % p[i] == 0){
            x /= p[i];
            z ++;
        }
        if(z)res = min(res,z);
    }
    if(x == 1)return res;
    for(int i=5;i>=2;i--){
        if(ok(x,i)){
            return res = min(res,i);
        }
    }
    return 1;
}
int main(){
    getP();
    int T;scanf("%d",&T);
    ll x;
    while(T--){
        scanf("%lld",&x);
        printf("%d\n",solve(x));
    }
    return 0;
}