寒假训练第一周
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