HPU算法协会一二年级联合训练赛
题目主要选自 Gym 100985A - Gym 100985M
简直就是阅读理解专场。。。
题意比题目还难。。。
一共13道题，勉强做出来12道，题目不难，题意难。
看来需要好好学学英语了。
A题：
题意介绍的很花哨，其实就是判断两个数的最大公因数是否为1。
刚开没能清楚的理解题意，其中题目中有一句是因数尽可能的少
- Each of these ids were chosen in a way such that they would have the least amount of divisors possible.
因为这一句我还以为是分解两个数的质因子，唉。。
// #include <bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// map<LL, LL> mp1, mp2;
// vector<LL> v1, v2;
// map<LL,LL> divd(LL x)
// {
// map<LL, LL> mp;
// LL cnt = 2;
// while(1)
// {
// while(x % cnt == 0)
// {
// x /= cnt;
// mp[cnt] ++;
// }
// cnt++;
// if(x == 1)
// break;
// }
// return mp;
// }
// int main()
// {
// int t;
// scanf("%d", &t);
// while(t--)
// {
// mp1.clear();
// mp2.clear();
// v1.clear();
// v2.clear();
// LL num1, num2;
// scanf("%lld %lld", &num1, &num2);
// mp1 = divd(num1);
// mp2 = divd(num2);
// int len1 = mp1.size();
// int len2 = mp2.size();
// map<LL, LL>::iterator it;
// for(it = mp1.begin(); it != mp1.end(); it++)
// {
// v1.push_back(it->first);
// }
// for(it = mp2.begin(); it != mp2.end(); it++)
// {
// v2.push_back(it->first);
// }
// int len = min(v1.size(), v2.size());
// bool flag = false;
// for(int i=0; i<len; i++)
// {
// if(v1[i] == v2[i])
// {
// flag = true;
// break;
// }
// }
// if(flag)
// printf("Sim\n");
// else
// printf("Nao\n");
// }
// return 0;
// }
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b)
{
return !b ? a : gcd(b, a%b);
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
LL num1, num2;
scanf("%lld %lld", &num1, &num2);
if(gcd(num1, num2) != 1)
printf("Sim\n");
else
printf("Nao\n");
}
return 0;
}
B题：
n个杯子，每个杯子上面有一个数，每次只能抽其中一个杯子，如果抽的杯子上面的数，不是游戏最后的答案还要继续抽，问一个人在最糟糕的情况下用最好的策略最少要抽几次？
题目描述的是这个意思，一直没想明白最好的策略是什么策略，我就假设结果是最后一个数，模拟二分的情况，二分了几次，就是抽多少次，结果就对了。。。。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
int cnt = 0;
while(n)
{
n = n / 2;
cnt ++;
}
printf("%d\n", cnt);
return 0;
} C题：
nim博弈，第一次取较多的堆，使两堆相等，下一次取完其中一堆。f
flush(stdout); 是题目要求加上去的。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x, y;
while(scanf("%d %d", &x, &y) != EOF)
{
if(x > y)
printf("%d %d\n", 1, x-y);
else if(x < y)
printf("%d %d\n", 2, y-x);
else if(x == y)
{
printf("%d %d\n", 2, y);
}
fflush(stdout);
}
return 0;
} D题：
不会。。
E题：
用前缀和数组。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N];
LL sum[N];
int main()
{
int n, m;
while(scanf("%d %d", &n, &m) != EOF)
{
memset(sum, 0, sizeof(sum));
sum[0] = 0;
for(int i=1; i <= n; i++)
{
scanf("%d", &a[i]);
sum[i] = sum[i-1] + a[i];
}
int l, r;
for(int i=0; i<m; i++)
{
scanf("%d %d", &l, &r);
LL ans = sum[r] - sum[l-1];
if(ans % 2 == 0)
printf("Sim\n");
else
printf("Nao\n");
}
}
return 0;
} F题：
题意难懂，其中还要向上取整，ceil()函数
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
// int percent;
// if(0.7 * n > (int) 0.7 * n)
// percent = 0.7 * n + 1;
// else
// percent = 0.7 * n;
int percent = ceil(0.7 * n);
int ans1 = 0, ans2 = 0;
if(percent > k)
ans1 = percent - k;
else
ans1 = 0;
ans2 = 100 * (k + n - m) / n;
if(ans2 < 70)
ans1 = -1;
printf("%d\n", ans1);
printf("%d\n", ans2);
return 0;
}
G题：
用栈，A入站，遇到B就将A出栈，栈里没有A就不能配对，如果最后栈不为空，也不能配对
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
char str[N];
stack<int> s;
int main()
{
while(!s.empty()) s.pop();
scanf("%s", str);
int len = strlen(str);
bool flag = false;
for(int i=0; i<len; i++)
{
if(str[i] == 'A')
s.push(1);
else if(str[i] == 'B')
{
if(!s.empty())
s.pop();
else
{
flag = true;
break;
}
}
}
if(flag || !s.empty())
printf("Nao\n");
else
printf("Sim\n");
return 0;
} H题：
求n维空间两点直接的距离，套用公式。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int a[N], b[N], c[N];
int main()
{
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
for(int j=0; j<n; j++)
scanf("%d", &b[j]);
for(int k=0; k<n; k++)
scanf("%d", &c[k]);
LL ab = 0;
for(int i=0; i<n; i++)
{
ab = ab + 1LL * (a[i] - b[i]) * (a[i] - b[i]);
}
LL ac = 0;
for(int i=0; i<n; i++)
{
ac = ac + 1LL * (a[i] - c[i]) * (a[i] - c[i]);
}
if(ab <= ac)
printf("Yan\n");
else
printf("MaratonIME\n");
return 0;
} I题：
正着和倒着比较, 一定要吃完才算
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++)
{
scanf("%d", &a[i]);
}
int cnta = 0, cntb= 0;
int suma = m, sumb = m;
for(int i=0; i<n; i++)
{
if(suma >= a[i])
{
cnta ++;
suma -= a[i];
}
else
break;
}
for(int i=n-1; i >= 0; i--)
{
if(sumb >= a[i])
{
cntb ++;
sumb -= a[i];
}
else
break;
}
// printf("%d %d\n", cnta, cntb);
if(cnta > cntb)
printf("Yan\n");
else if(cnta < cntb)
printf("Nathan\n");
else
{
printf("Empate\n");
}
return 0;
} J题：
判断几个圆相切或相交，如果有，就把这样的成对输出。
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
typedef long long LL;
typedef pair<int, int> P;
struct node{
int x, y, r;
};
struct node cle[N];
vector<P> v;
int main()
{
int n;
scanf("%d", &n);
for(int i=1; i <= n; i++)
{
scanf("%d %d %d", &cle[i].x, &cle[i].y, &cle[i].r);
}
v.clear();
for(int i=1; i<=n; i++)
{
for(int j=i+1; j<=n; j++)
{
double dis = sqrt(pow(1.0 * cle[i].x - cle[j].x, 2) + pow(1.0 * cle[i].y - cle[j].y, 2));
if(dis <= cle[i].r + cle[j].r)
v.push_back(P(i, j));
}
}
// printf("%d %d", v[0].first, v[0].second);
int len = v.size();
for(int i=0; i<len; i++)
{
printf("%d %d ", v[i].first, v[i].second);
}
printf("\n");
return 0;
} K题：
字符串简写
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
char s[N];
// int a[N];
int main()
{
scanf("%s", s);
int len = strlen(s);
for(int i=0; i<len; i++)
{
int j = i;
int cnt = 0;
for(j=i; j<len; j++)
{
if(s[j] == s[i])
cnt ++;
else
break;
}
printf("%c%d", s[i], cnt);
i = j-1;
}
return 0;
} L题：
找出最大数，一定要是最大，不能有并列
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
int maxnum = -1;
int index = -1;
for(int i=0; i<n; i++)
{
scanf("%d", &a[i]);
if(maxnum < a[i])
{
maxnum = a[i];
index = i;
}
}
int cnt = 0;
for(int i=0; i<n; i++)
{
if(maxnum == a[i])
{
cnt ++;
}
}
if(cnt > 1)
printf("-1");
else
printf("%d\n", index + 1);
}
return 0;
} M题：
按指定格式，把一个矩阵给遍历一遍，vector要预处理一个0，不然会RE
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
char mp[N][N];
vector<int> v;
int main()
{
int n, m;
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++)
{
scanf("%s", mp[i]);
}
v.clear();
v.push_back(0);
int money = 0;
for(int i=0; i<n; i++)
{
int j;
if(i % 2 == 0) j = 0;
else j = m-1;
if(j == 0)
{
for(j = 0; j<m; j++)
{
if(mp[i][j] == '.')
money ++;
else if(mp[i][j] == 'L')
{
v.push_back(money);
money = 0;
}
}
}
else if(j == m-1)
{
for( ; j >= 0; j--)
{
if(mp[i][j] == '.')
money ++;
else if(mp[i][j] == 'L')
{
v.push_back(money);
money = 0;
}
}
}
}
sort(v.begin(), v.end());
printf("%d\n", v[v.size() - 1]);
return 0;
}
腾讯泡池子938人在聊