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
", anss);
for(int i = 2; i <= n; i++) {
if(i != n) printf("%d ", ans[i]);
else printf("%d
", 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 (nover k)is even, you can find solution quite easily.
If (nover 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 (nover k)is even.
Time complexity is (O(n)).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
ll n,k;
vector<int> 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<n/k;j++){
printf(" %d",ans[i][j]);
//sum += ans[i][j];
}
//printf(" sum = %d",sum);
puts("");
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)ans[i].clear();
if(n*(n+1)/2 % k != 0){
puts("no");
continue;
}
puts("yes");
long long sum = n*(n+1)/2 / k;
//cout<<sum<<endl;
if((n/k)%2 == 0){
solve(1,n,k);
print();
}
else{
ll sum = (1+3*k)*(3*k)/2/k;
for(int i=1;i<=k;i++){
ans[i].push_back(i);
int se = 0;
if(i & 1){
se = k + k / 2 + 1 - i / 2;
}else{
se = 2 * k + 1 - i / 2;
}
ans[i].push_back(se);
ans[i].push_back(sum-i-se);
}
if(3*k<n)
solve(3*k+1,n,k);
print();
}
}
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^{1over 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
",solve(x));
}
return 0;
}