2021年度训练联盟热身训练赛第二场
链接：https://ac.nowcoder.com/acm/contest/12794
这一场似乎是全是原题？群里看了有人发的pdf题面上写着UCF Aug,2016
A：
题意：输出一个大于等于n的2次幂数
代码：
while (t--) {
int n; cin >> n;
cout << "Input value: " << n << endl;
int t = 1;
while (t < n) t *= 2;
cout << t << endl << endl;;
} B： 题意：可将指定的字符串替换成另外一个特定字符串，输出最后结果。
思路：用两个map标记一下。
代码：
map<string,string>mp;
map<string,int>mmp;
int main() {
int t; cin >> t;
while(t--)
{
string s; cin >> s;
getchar();
string a; getline(cin,a);
mp[s]=a;
mmp[s]=1;
}
int n; cin >> n;
while(n--)
{
string ss;
while(cin>>ss){
char c=getchar();
if(c=='\n'){
if(mmp[ss]) cout<<mp[ss];
else cout<<ss;
break;
}else{
if(mmp[ss]) cout<<mp[ss]<<" ";
else cout<<ss<<" ";
}
}
cout<<endl;
}
return 0;
} C：一开始读了假题，以为小费就是当前cost*20%，结果样例都不对。。。然而一个队友当时在开b，另一个队友还在龙抬头剪头发，是组里另外一个人点了我一下。
题意：判断当前消费的金额是否是回文，是就直接cost*20%向上取整输出，再输出cost，否则的话不断增加小费直至总花费为回文。
代码：
#include <bits/stdc++.h>
using namespace std;
bool check(int x)
{
int sum=0;
if(x<0 || (x/10!=0 && x%10==0))
{
return false;
}
else{
while(x>sum)
{
sum = sum * 10 + x%10;
x = x/10;
}
}
/*若整数为偶数*/
if(sum == x)
{
return true;
}
/*若整数位数为奇数*/
if(sum/10 == x)
{
return true;
}
return false;
}
int main() {
int t; cin >> t;
while(t--)
{
int n; cin >> n;
int tmp=ceil(1.0*n/5);
int temp=tmp+n;
while(!check(tmp+n))
{
tmp++;
}
cout << "Input cost: " << n << endl;
cout << tmp << " " << tmp+n << endl << endl;
}
return 0;
}
D：队友写的，他说不难，就模拟。 代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<vector>
#include<map>
#include<string>
#include<stdio.h>
#include<set>
#define ll long long
#define mod 1e9+7
#define MAXN 100005
#define repa(a, b) for (a = 0; a < b;a++)
#define repd(a, b) for (a = b; a >= 0;a--)
using namespace std;
ll gcd(ll a,ll b){
return (!b)?a:gcd(b,a%b);
}
ll qpow(ll a, ll b,ll m) {
ll temp = a%m;
a = 1;
while (b) {
if (b % 2 != 0)a = (a * temp)%m;
temp = (temp * temp)%m;
b >>= 1;
}
return (ll)(a%m);
}
ll lowbit(ll x) {
return x & (-x);
}
struct node{
string name;
ll points;
ll wins;
ll losses;
ll draws;
ll goals_scored;
ll goals_allowed;
}li[1000];
map<string, node*> mp;
int cmp(node a,node b){
if(a.points != b.points)
return a.points >= b.points;
else if(a.goals_scored - a.goals_allowed != b.goals_scored - b.goals_allowed)
return (a.goals_scored - a.goals_allowed) >= (b.goals_scored - b.goals_allowed);
else if(a.goals_scored != b.goals_scored)
return a.goals_scored >= b.goals_scored;
else
return a.name < b.name;
}
int main(){
int t;
cin >> t;
int g = 1;
while(g <= t){
int n, m;
cin >> n>>m;
string s;
memset(li, 0, sizeof(li));
for (int i = 0; i < n;i++){
cin >> s;
mp[s] = &li[i];
mp[s]->name = s;
}
string a, b;
ll c, d;
for (int i = 0; i < m;i++){
cin >> a >> c >> b >> d;
if(c > d){
mp[a]->wins++;
mp[a]->points += 3;
mp[a]->goals_scored += c;
mp[a]->goals_allowed += d;
mp[b]->goals_scored += d;
mp[b]->goals_allowed += c;
mp[b]->losses++;
}else if(d > c){
mp[b]->wins++;
mp[b]->points += 3;
mp[b]->goals_scored += d;
mp[b]->goals_allowed += c;
mp[a]->goals_scored += c;
mp[a]->goals_allowed += d;
mp[a]->losses++;
}else{
mp[a]->draws++;
mp[b]->draws++;
mp[a]->points++;
mp[b]->points++;
mp[a]->goals_scored += d;
mp[a]->goals_allowed += c;
mp[b]->goals_scored += c;
mp[b]->goals_allowed += d;
}
}
sort(li, li + n, cmp);
printf("Group %d:\n", g);
for (int i = 0; i < n;i++){
cout << li[i].name;
printf(" %lld %lld %lld %lld %lld %lld\n", li[i].points, li[i].wins, li[i].losses, li[i].draws, li[i].goals_scored, li[i].goals_allowed);
}
g++;
cout << endl;
mp.clear();
}
return 0;
} E：
题意：有那么多钱，每花费一定钱可以救一定数量的人，问最多能救多少人。
思路：01背包。
代码：
F：队友开的，就并查集判环，本来可以一遍过循环开小了，只循环到n，然后改成10000就过了，总过就用了n个点，不懂干嘛要循环那么多次，迷之操作。。。
const int N =1e5+5;
int dp[15][N];
int main()
{
int t; cin >> t;
int cnt=1;
while(t--)
{
int d,B; cin >> d >> B;
memset(dp,0,sizeof(dp));//一开始忘记初始化，卡了好久。。。
for(int i=1;i<=d;i++)
{
for(int j=1;j<=4;j++)
{
int v,w; cin >> v >> w;
for(int k=0;k<=B;k++)
{
if(k>=v) dp[i][k]=max(max(dp[i-1][k],dp[i-1][k-v]+w),dp[i][k]);
else dp[i][k]=max(dp[i-1][k],dp[i][k]);
}
}
}
cout << "Budget #" << cnt++<<": Maximum of "<<dp[d][B]<<" lives saved.";
cout<<endl<<endl;
}
return 0;
} F：队友开的，就并查集判环，本来可以一遍过循环开小了，只循环到n，然后改成10000就过了，总过就用了n个点，不懂干嘛要循环那么多次，迷之操作。。。
代码：（并查集的实现就不贴了）
while (t--) {
int n, m; cin >> n >> m;
int vis[10010], p[10010], check[10010];
rep(i, 1, 10000) fat[i] = i, vis[i] = check[i] = p[i] = 0;//就这个循环！！！
int u[10010], v[10010];
int ans = 0;
rep(i, 1, m) {
cin >> u[i] >> v[i];
check[u[i]] = check[v[i]] = 1;
if (!mix_f(u[i], v[i])) vis[i] = 1;
}
rep(i, 1, m) {
int rt1 = find_f(u[i]);
int rt2 = find_f(v[i]);
if (rt1 == rt2) {
if (vis[i] && !p[rt1]) ans++, p[rt1] = 1;
}
}
int cnt = 0;
rep(i, 1, n) {
if (fat[i] == i && check[i]) cnt++;
}
cout << "Night sky #" << c++ << ": " << cnt << " constellations, of which " << ans << " need to be fixed." << endl << endl;
} G：
题意：一个人从当前位置移动到下一个位置所在的盘子所需的时间是0.5秒，盘子都是有一定的初速度，速度每秒减5，当速度为0时盘子会掉落，如果一圈后盘子速度正好为0，盘子不会掉落，问最后盘子是否会掉落。
思路：判断一下盘子的初速度与走一圈之后减少的速度的大小关系，大于等于就满足条件，否则盘子会掉落。注意！！！特判n==1！！！
代码：
while (t--) {
cout << "Circus Act " << cnt++ << ":" << endl;
int n, p; cin >> n >> p;
if(n==1){
cout << "Chester can do it!" << endl;
cout<<endl;
continue;
}
double ans = (n) * 2.5;
if (p-ans<0) cout << "Chester will fail!" << endl;
else cout << "Chester can do it!" << endl;
cout << endl;
} H： 题意：enm...就是大模拟，约束条件太多，队友一开始用的搜索去写tle
I:
题意：给你三个点 圆心和圆上两点，问逆时针的圆弧和该从圆上两点中任意一点从圆内出发到另外一点的距离哪种方法要短。
思路：算两个的路径比大小，圆内就是多个点的距离之和，圆弧就涉及到一些基础的数学知识，求半径、圆心角、计算弧长。这道题和队友同时开的，结果它在计算多个点的距离和时忘记更新x，y值了。
代码
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#define PI acos(-1.0)
using namespace std;
struct P{
double x,y;
};
double S(double x1,double y1,double x2,double y2,double x3,double y3)
{
return (x2-x3)*(y1-y3)-(y2-y3)*(x1-x3);
}
double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
double x0,x1,x2,y0,y1,y2;
double r,ab,k,b,h,so,C,l,O,s;int T=1;
while(scanf("%lf%lf%lf%lf%lf%lf",&x0,&y0,&x1,&y1,&x2,&y2)!=EOF)
{
if(x0==0&&y0==0&&x1==0&&x2==0&&y1==0&&y2==0) break;
//圆心和圆上两点
r=sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0));
double r2=(x1-x0)*(x1-x0)+(y1-y0)*(y1-y0);
ab=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
double ab2=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
double co=(2*r2-ab2)/(2*r2);
O=acos(co);
if(fabs(ab-2*r)<1e-6)
{
l=PI*r;
}
else
{
if(O>PI)
O=2*PI-O;
l=O*r;
}
int n; cin >> n;
double ans1=0;
double x = x1, y = y1;
for(int i=1;i<=n;i++) {
double tx, ty;
cin >> tx >> ty;
ans1 += dis(x, y, tx, ty);
x=tx,y=ty;//队友就是忘了这里
}
ans1 += dis(x, y, x2, y2);
if(l>ans1)
printf("Case #%d: Watch out for squirrels!\n",T++);
else
printf("Case #%d: Stick to the Circle.\n",T++);
puts("");
}
return 0;
}
J：
题意：在完全二叉树中，给两个结点的位置，求出它们最近的公共祖先（lca）,输入为十六进制，输出为十六进制。
思路：其实就是二进制的题目。比如5和9它们的lca是2。5的二进制101、9的二进制1001；它们最长公共前缀是10，也就是2。我们只需要将十六进制转化为二进制去求它们的最长公共前缀，最后再转为十六进制即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int a[1000],b[1000],a1[4000],b1[4000],c[4000];
int main()
{
int t,i,j,k,temp;
string str1,str2;
cin>>t;
int asd = 1;
while(asd <= t)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(a1,0,sizeof(a1));
memset(b1,0,sizeof(b1));
memset(c,0,sizeof(c));
cin>>str1>>str2;
int len1=str1.size(),len2=str2.size();
for(i=0;i<len1;i++)//字符串存到数字数组里，方便进制转换
{
if(str1[i]>='a'&&str1[i]<='f')
a[i]=(str1[i]-'a')+10;
else if(str1[i]>='0'&&str1[i]<='9')
a[i]=int(str1[i]-'0');
}
for(i=0;i<len2;i++)
{
if(str2[i]>='a'&&str2[i]<='f')
b[i]=(str2[i]-'a')+10;
else if(str2[i]>='0'&&str2[i]<='9')
b[i]=int(str2[i]-'0');
}
for(i=0;i<len1;i++)//16进制转二进制
{
j=(i+1)*4;
temp=0;
while(a[i]!=0)
{
a1[j]=a[i]%2;
a[i]=a[i]/2;
j--;
temp++;
}
while(temp<4)
{
a1[j]=0;
j--;
temp++;
}
}
for(i=0;i<len2;i++)
{
j=(i+1)*4;
temp=0;
while(b[i]!=0)
{
b1[j]=b[i]%2;
b[i]=b[i]/2;
j--;
temp++;
}
while(temp<4)
{
b1[j]=0;
j--;
temp++;
}
}
len1=len1*4,len2=len2*4;
k=0;
i=1,j=1;
//存最长公共前缀
while(a1[i]==0)
i++;
while(b1[j]==0)
j++;
for(;i<=len1&&j<=len2;i++,j++)
{
if(a1[i]==b1[j])
{
c[k]=a1[i];
k++;
}
else
break;
}
//转十六进制
int num=0,f=0;
char ch[1000],sh='a';
for(i=k-1;i>=0;)
{
num=0;
temp=4;
while(temp--)
{
num+=c[i]*pow(2,3-temp);
i--;
}
if(num>=10)
ch[f]=sh+(num-10);
else
ch[f]=num+48;
f++;
}
//输出数据
cout<<"Case #"<<asd++<<": ";
for(i=f-1;i>=0;i--)
cout<<ch[i];
cout<<endl;
cout<<endl;
}
}
