2021.12.20

今天cf背景没有雪花了QAQ）链接（不全待补）

A. Square String?

主要意思是说形如“x”“x”两部分相连的一个字符串为square字符串（x可以为任意字符串，任意长度但不能为0），给出一个字符串，判断是否为square字符串。

**思路：**可分为两种情况：若字符串长度为奇数，则必不满足；若为偶数，直接判断。

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t;
string s;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>s;
    	if(s.length()%2)
    	cout<<"NO"<<'\n';
    	else 
    	{
    		int len=s.length();
    		string c1=s.substr(0,len/2);
    		string c2=s.substr(len/2,len/2);
    		if(c1==c2)
    		cout<<"YES"<<'\n';
    		else
    		cout<<"NO"<<'\n';
		}
	}
	return 0;
}

废话可跳过：A题要快！！！不过英语水平限制了我的速度www

B. Squares and Cubes

主要意思是给出一个数字n，找出1~n中平方数、立方数的个数。

**思路：**通过找规律可发现某些平方数与立方数是重叠的，可以将平方数与立方数相加，减去重叠数得到答案。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t,n; 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	cout<<(int)sqrt(n)+(int)cbrt(n)-(int)sqrt(cbrt(n))<<'\n';
	}
	return 0;
}

废话可跳过：sqrt()开平方根，cbrt()开立方根，开立方根这个我才知道（一开始写了好多行代码。。。）

点击并拖拽以移动编辑：P

C. Wrong Addition

主要意思是一种错误的竖式加法，要完成的任务是加法的逆运算。

**思路：**从最后一位开始，a与s之间计算，注意有b不存在的情况，即两数相加结果“大于20”和循环结束后a、s仍不全为0。一个模拟题。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
ll t,a1,a2;
ll a,s;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>a>>s;
    	ll b=0,c=1;
    	while(a>0||s>0)
    	{
    		a1=a%10;
    		a2=s%10;
    		if(a1>a2)
    		{
    			if((s%100)/10==1)
    			{
    				s/=10;
    				a2+=10;
				}
				else break;
			}
			b+=(a2-a1)*c;
			c*=10;
			a/=10,s/=10;
		}
		if(a>0||s>0)
		cout<<"-1"<<'\n';
		else
		cout<<b<<'\n';
	}
	return 0;
}

废话可跳过：为什么总是有一个大致的方向然后细节搞不定啊。。。

D. New Year’s Problem

主要意思是给一个m*n的矩阵，最多选择n-1行，每列选一个，使得所选值得最小值最大。

**思路：**二分查找。有两种情况：1、若m<=n-1，则可以全选，直接判断每一列最小值即可；

2、若m>n-1，则至少有一个商店要买至少两件礼物，则对每个人礼物的最大值进行二分查找得到最小值即可。参考

AC代码：（学习了参考资料里的代码写法，但是我感觉参考资料里的表述有点问题。。。）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e6+5;
ll t,n,m;

vector<ll>a[N];

bool pan(ll x)
{
	for(ll i=0;i<m;i++)
	{
		ll add=0;
		for(ll j=0;j<n;j++)
		{
			if(a[i][j]>=x)
			add++;
		} 
		if(add>=2)
		return 1;
	}
	return 0;
}

void work()
{
	ll l=0,r=1e9+3;
	for(ll j=0;j<n;j++)
	{
		ll ma=0;
		for(ll i=0;i<m;i++)
		ma=max(ma,a[i][j]);
		r=min(ma,r);
	}
	if(m>n-1)
	{
		while(l<=r)
	    {
		    ll mid=(l+r)>>1;
		    if(pan(mid))
		    l=mid+1;
		    else r=mid-1;
	    }
	    cout<<r<<'\n';
	}
	else cout<<r<<'\n';
	return;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>m>>n;
    	for(ll i=0;i<m;i++)
    	{
    		a[i].clear();
    		for(ll j=0;j<n;j++)
    		{
    			ll x;
    			cin>>x;
    			a[i].push_back(x);
			}
		}
		work();
	}
	return 0;
}

废话可跳过：原来出现n*m范围大小的矩阵可以用vector，，，我对不起讲课的师哥们我才知道。。。

E. MEX and Increments

主要意思是给定数组，对任意元素进行任意次+1操作，是的其MEX值为0~n，求最少操作次数，MEX为不在数组中的最小非负数。

**思路：**首先要清楚的一点是每一个MEX值都与前一个有关，即MEX=n+1与MEX=n有关。统计每个数字在数组的出现次数，当MEX的值与数组中出现数字相同时，应该先将每个数字+1，使该数字成为较小值；还需要考虑满足前面的数字没有比该数字小的，所以要加上差值tmp；而这个差值仅在MEX值为数组中未出现的数时改变。细节在注释中。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2*1e5;
ll t,n;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	ll a[n]={0},b[N+10]={0};
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a[i];
    		b[a[i]]++;
		}
    	stack<int>sta;//利用栈实现按照0~n顺序
    	ll tmp=0,x=0;
    	for(int i=0;i<=n;i++)
    	{
    		if(x==-1) cout<<"-1"<<' ';
    		else if(b[i]>0)
    		{
    			for(int j=0;j<b[i]-1;j++)
    			sta.push(i);
    			cout<<tmp+b[i]<<' ';
			}
			else
			{
				cout<<tmp<<' ';
				if(sta.size()==0)
				x=-1;//若某个MEX值在数组中不存在，且此时没有更多的次小值可供操作，则不满足
				else   //条件，再大的MEX值也都不能通过操作得到了
				{
					tmp+=i-sta.top();//该操作的目的是满足操作次数最少，即对次小值操作，
					sta.pop();       //若次小值大于一个，则对次小值操作，保证操作次数最少
				}                   
			}
		}
		cout<<'\n';
	}
	return 0;
}

废话可跳过：看别人的AC代码理解了好久，算法很巧妙~

若有错误请赐教

Orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

20211220cf补题（不全待补）

A. Square String?

B. Squares and Cubes

C. Wrong Addition

D. New Year’s Problem

E. MEX and Increments

FEATURED TAGS

FRIENDS