寒假训练第一周
1.6日codeforces训练赛
A题 Medium Number
这道题的思路很简单,主要是一个多次输入的条件。这道题解题方式有多种,我是通过一个sort函数进行排序,然后输出第二个数就可以了。
#include<bits/stdc++.h>
using namespace std;
int main(){
int a;
cin >> a;
while(a--){
int b[4];
for(int i=0;i<3;i++){
cin >> b[i];
}
sort(b,b+3);
cout << b[1] << "\n";
}
return 0;
}
B题 Yes-Yes?
这道题的思路是通过一个find函数看输入的的字符串是不是能够在一个标准字符串中找到。然后判断条件是a.find(b)!=-1;a是标准字符串,b为输入字符串,代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int t;
cin >> t;
while(t--)
{
string a = "YesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYesYes";
string b;
cin >> b;
if(a.find(b)!=-1)
cout << "YES\n" ;
else
cout << "NO\n" ;
}
return 0;
}
C题 Atilla's Favorite Problem
这道题的思路就是通过一个for循环输入一个字符串数组c[i],c[i]-96就是字母表中的位置,然后通过max来比较大小。代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
int a;
cin >> a;
while(a--){
int b,max=0;
cin >> b;
char c[100];
for(int i=0;i<b;i++){
cin >> c[i];
if(c[i]-96>max)
max=c[i]-96;
}
cout << max<< "\n";
}
return 0;
}
D题 Lost Permutation
这道题的思路将输入的数字进行一个标记,然后再通过一个sum,将未输出的数字加起来,然后通过比较sum与n的大小比较再进行一次判断,然后通过一个计数器cnt来统计出一共合格的数字。代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
int a;
cin >> a;
while(a--){
int m,n,x;
cin >> m >> n;
int b[110]={0};
for(int i=1;i<=m;i++){
cin >> x;
b[x]=1;
}
int cheak=0,sum=0,cnt=0;
for(int i=1;;i++){
if(b[i]==0){
sum+=i;
cnt++;
b[i]=1;
}
if(sum==n)
break;
if(sum>n){
cheak=1;
break;
}
}
for(int i=1;i<=m+cnt;i++){
if(b[i]==0){
cheak=1;
break;
}
}
if(cheak==1)
cout << "NO\n";
else
cout << "YES\n";
}
return 0;
}
Challenging Valleys
这道题的思路就是通过一个判断cheak,看之前是不是出现了谷点,然后看后面是不是还会出现峰点,如果后面又一次出现了谷点,则直接退出循环,输入no。代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
int a;
cin >> a;
while(a--){
int b,cheak=0,mo=0;
cin >> b;
int c[b+2];
for(int i=0;i<b;i++){
cin >> c[i];
}
for(int j=1;j<b;j++){
if(c[j-1]<c[j])
cheak=1;
if(c[j-1]>c[j]&&cheak==1){
mo=1;
break;
}
}
if(mo==1)
cout << "No\n";
else
cout << "Yes\n";
}
return 0;
}
F题 Binary Inversions
这道题的思路就是通过一个枚举,三种情况,一种是不变,再一种是将最前面的0变为1,最后一种是将最后的1变为0,然后比较三个数的max值,因为这道题的值比较小,这样的输出是可以满足条件的。代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
long long int a;
cin >> a;
while(a--){
int b;
cin >> b;
long long int c1[b+1],c2[b+1],c3[b+1],cnt1=0,cnt2=0,cnt3=0,sum=0;
for(int i=0;i<b;i++){
cin >> c1[i];
c2[i]=c1[i];
c3[i]=c1[i];
}
for(int i=0;i<b;i++){
if(c2[i]==0){
c2[i]=1;
break;
}
}
for(int i=b-1;i>=0;i--){
if(c3[i]==1){
c3[i]=0;
break;
}
}
for(int i=0;i<b;i++){
if(c1[i]==0){
cnt1+=sum;
}else
sum++;
}
sum=0;
for(int i=0;i<b;i++){
if(c2[i]==0){
cnt2+=sum;
}else
sum++;;
}
sum=0;
for(int i=0;i<b;i++){
if(c3[i]==0){
cnt3+=sum;
}else
sum++;
}
cout << max(cnt1,max(cnt3,cnt2))<<"\n";
}
return 0;
}
还需要注意的是,需要注意变量类型,如果是int的话数据就会越界。
G题 Quests(补题)
这道题可以说当时写的时候完全没有思路,之后听了别人的讲解之后,发现可以用二分的思想去解决问题但是判断的条件怎么写,还是没有思路,然后去看了别人的题解,发现还要用到前缀和和贪心的知识,然后根据别人的代码,自己写了一遍,代码如下:
#include<bits/stdc++.h>
using namespace std;
bool cmp(long long int a,long long int b){
return a>b;
}
int main()
{
long long int t;
cin >> t;
while(t--)
{
long long int n,c,d;
cin >> n >> c >> d;
long long int a[n+1];
for(long long int i=0;i<n;i++){
cin >> a[i];
}
sort(a,a+n,cmp);
long long int left=0,right=d;
while(left<=right){
long long int mid=(left+right)/2,cnt=0;
for(long long int i=0;i<d;i++){
long long int id = i % (mid + 1);
if(id < n)
cnt += a[id];
}
if(cnt >= c)
left = mid + 1;
else
right = mid - 1;
}
long long int id = left - 1;
if(id == d){
cout << "Infinity\n";
}else if(id == -1){
cout << "Impossible\n";
}else{
cout << id << "\n" ;
}
}
return 0;
}
H题SlavicG's Favorite Problem
这道题是加权树类型的题,但是还是没有啥思路,额...加权树那部分没学懂,补题的时候也不太会,下面是别人的代码题解,自己的代码,等学懂之后再补充。
#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+10;
typedef pair<int,int>PII;
int n,a,b;
vector<PII>ve[N];
set<int>se;
bool ok;
void dfs1(int u, int fa, int sum){
se.insert(sum);
for(auto [x, y] : ve[u]){
if(x == fa) continue;
if(x != b)
dfs1(x, u, sum ^ y);
}
}
void dfs2(int u, int fa, int sum){
for(auto [x, y] : ve[u]){
if(x == fa) continue;
if(se.count(sum ^ y)) ok = 1;
dfs2(x, u, sum ^ y);
}
}
void solve(){
cin >> n >> a >> b;
ok = false;se.clear();
for(int i = 1; i <= n; i ++ ) ve[i].clear();
for(int i = 1; i <= n - 1; i ++ ){
int x, y, z;cin >> x >> y >> z;
ve[x].push_back({y, z});
ve[y].push_back({x, z});
}
dfs1(a, 0, 0);dfs2(b, 0, 0);
if(ok) cout << "YES\n";
else cout << "NO\n";
}
signed main(){
int T;cin>>T;
while(T--) solve();
}
I题The Humanoid
这道题当时的思路就很简单了,先是对输入的数组进行一个sort排序,然后再从小到大进行一个判断,能击败,能击败的话,就得到一半的能量值。然后就如果不能吃下去的话,就可以喝能量药水了,喝的顺序有223 322 232三种,然后分别比较取最大值就可以了输出了。代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
long long int a;
cin >> a;
while(a--){
long long int n ,h;
cin >> n >> h;
long long int x=0,x1=0,x2=0,x3=0,y[n+2],h1;
h1=h;
for(int i=1;i<=n;i++){
cin >> y[i];
}
sort(y+1,y+1+n);
int yao=1;
for(int i=1;i<=n;i++){
if(h>y[i]){
x1++;
h+=y[i]/2;
}
else{
if(yao==1){
h*=2;
i--;
yao++;
}
else if(yao==2){
h*=2;
i--;
yao++;
}
else if(yao==3){
h*=3;
i--;
yao++;
}
else
break;
}
}
x=max(x,x1);
h=h1;
yao=1;
for(int i=1;i<=n;i++){
if(h>y[i]){
x2++;
h+=y[i]/2;
}
else{
if(yao==1){
h*=2;
i--;
yao++;
}
else if(yao==2){
h*=3;
i--;
yao++;
}
else if(yao==3){
h*=2;
i--;
yao++;
}
else
break;
}
}
x=max(x,x2);
h=h1;
yao=1;
for(int i=1;i<=n;i++){
if(h>y[i]){
x3++;
h+=y[i]/2;
}
else{
if(yao==1){
h*=3;
i--;
yao++;
}
else if(yao==2){
h*=2;
i--;
yao++;
}
else if(yao==3){
h*=2;
i--;
yao++;
}
else
break;
}
}
x=max(x,x3);
cout << x << "\n";
}
return 0;
}
J题Make It Round
这道题就是通过看2 5的数量,如果2的数量大于5,就补充5的倍数,如果大于可以增加的最大倍数,就退出循环,反之亦然,然后再补充10的倍数,直接模拟就可以了,代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
long long int a;
cin >> a;
while(a--){
long long int n,m,x,y,cnt1=0,cnt2=0,mo=1;
cin >> n >> m;
x=n,y=n;
while(1){
if(x%2!=0){
break;
}
else
{
cnt1++;
x/=2;
}
}
while(1){
if(y%5!=0){
break;
}
else
{
cnt2++;
y/=5;
}
}
while(1){
if(cnt1<cnt2){
if(mo*2>m)
break;
else{
cnt2--;
mo*=2;
}
}
else if(cnt1>cnt2){
if(mo*5>m)
break;
else{
cnt1--;
mo*=5;
}
}
else
break;
}
while(1){
if(mo*10>m)
break;
else
mo*=10;
}
cout << m/mo*mo*n << "\n";
}
return 0;
}
K题Thermostat(补题)
这道题当时是没啥思路的,后面听了别人的讲解和代码,发现这个其实也可以通过模拟进行解决,先找出初始温度到目标温度是不是大于或等于x,不符合又看初始温度a到两边边界的差的绝对值是不是>=x,再进行一次判断,然后多次累加,但是最多只有三次,多了之后就会陷入死循环,因为一直不可能达到目标,然后自己根据别人的代码自己写了一遍,代码如下:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
long long int l,r,x,a,b;
cin >> l >> r >> x;
cin >> a >> b;
if(a==b)
{
cout << 0 << "\n";
continue;
}
int sum=1;
int cheak=0;
long long int mo = abs(a-b);
while(mo<x)
{
sum++;
int x1 = max(a-l,r-a);
if(sum>4||x1<x)
{
cheak=1;
break;
}
mo = 0;
int a1 = a;
if(a-l>=x)
{
a = l;
mo = abs(a-b);
}
if(r-a1>=x&&r-b>mo)
{
a = r;
mo = abs(a-b);
}
}
if(cheak==1)
cout << -1 << "\n";
else
cout << sum << "\n";
}
return 0;
}
L题Advantage
这道题的思路很简单,我是通过一个sort函数取出最大值以及第二大的值,然后遍历看数字判断出最大值,然后再遍历数组看数组中的这个元素是不是max,如果不是,则用这个元素-max,如果是max,则用max-第二大的数字。代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
int a;
cin >> a;
while(a--){
long long int b;
cin >> b;
long long int c[b+1],max=0,d[b+1];
for(long long int i=0;i<b;i++){
cin >> c[i];
d[i]=c[i];
if(c[i]>max)
max=c[i];
}
sort(d,d+b);
for(long long int i=0;i<b;i++){
if(c[i]!=max)
cout << c[i]-max << " ";
if(c[i]==max)
cout << max-d[b-2] << " ";
}
cout << "\n";
}
return 0;
}
因为这个数据并不是很大,所以很多题都可以暴力枚举。
标签:1.6,int,cf,long,cin,--,yao,寒假,else From: https://www.cnblogs.com/molinyuni/p/17034692.html