2019 Multi-University Training Contest 4

Solved	Pro.ID	Title	Ratio(Accepted / Submitted)
	1001		31.75%(1018/3206)
	1002		0.00%(0/105)
已补	1003		10.35%(126/1217)
	1004		0.00%(0/125)
	1005		17.65%(9/51)
	1006		29.03%(18/62)
	1007		31.83%(875/2749)
队友已补	1008		10.97%(376/3429)
	1009		0.00%(0/35)
已补	1010		6.15%(328/5331)

1001

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

#include 
    
     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;}
    

1003

If the total number of stones is a multiple of \(k\), we can always divide the stones. Otherwise, we can’t.

If \(n\over k\)is even, you can find solution quite easily.

If \(n\over k\) is an odd number, we divide first \(3k\) stones into \(k\) groups with exactly \(3\) stones and equal weight.

After that, you can divide remaining stones by the way you did when \(n\over k\)is even.

Time complexity is \(O(n)\).

#include 
    
     using namespace std;typedef long long ll;int  T;ll n,k;vector
     
       ans[100010];void solve(int l,int r,int k){    for(int i=1;i<=k;i++){        for(int j=0;j<(r-l+1)/2/k;j++){            ans[i].push_back(l+2*k*j + i-1);            ans[i].push_back(l+2*k*j + 2*k-i);        }    }}void print(){    for(int i=1;i<=k;i++){        //int sum = ans[i][0];        printf("%d",ans[i][0]);        for(int j=1;j
     
    

1007

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

#include 
    
     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 
    
     using namespace std;typedef long long ll;const int N = 1500;int p[N],v[N],tot;void getP(){    for(int i=2;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;}