Codeforces补题

Problem - C - Codeforces

23.11.7晚div2

题目大意： 

给定一个序列，长度为n，可以对它做k次操作。

定义fixed point 为ai=i；

定义操作为每次选择一个fixed point ai左移i下

我们只需要判断是否能构造一个序列a使其经过n次操作后得到b。

思路：

 根据这个性质就很容易反推了，每次我们看最后一个数，只要是小于n的那么就合法，看k次就好了。（看漏条件真的很要命。。

如果做了n次操作就会回到之前的答案，因此我们实际上只需要做k%n次操作，但是检验时需要检验min（n，k）次。没有这个剪枝会超时。

 
#include
const int N=2e5+10;
int a[N];
void solve()
{
	memset(a,0,sizeof a);
	int n,k;
	std::cin>>n>>k;
	for(int i=1;i<=n;i++) std::cin>>a[i];
	k=std::min(n,k);
	int last=n;
	while(k--)
	{
		if(a[last]>n)
		{
			std::cout<<"No\n";
			return ;
		}
		last=(last-a[last]+n)%n;
	}
	std::cout<<"Yes\n";
}
signed main()
{
	int t;std::cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Problem - B - Codeforces

vp2

题目大意： 

A对应1，AA对应27，以此类推。

数据有两种格式RXCY，（26进制）YX

现在输入中有这两种格式，进行转换。

模拟就好了。

值得注意的是对这种字符串数字转换问题不能限定长度，必须要用while循环读入，熟悉一下stoi函数的使用，将字符串转为数字。 

#include
#define int long long
void solve()
{
	std::string s;
	std::cin>>s;
	int i=0;
	std::string str;
	while(isalpha(s[i]))
	{
		str+=s[i];
		i++;
	}
	if(str=="R")
	{
		//继续判断后面有没有字符
		std::string num;
		while(isdigit(s[i]))
		{
			num+=s[i];	
			i++;
		}
		if(i==s.size())//字母数字型 
		{//R23
			int ans='R'-'A'+1; 
			std::cout<<"R"<stoi(num)<<"C"<'\n';
			//把字母转化成数字	BC->55
			/*int ans=0;
			for(auto i:str)
			{
				ans=ans*26+(i-'A'+1);	
			} 
			std::cout<
		}else{//RX==num CY
			i++;//跳过C 
			std::string num2;
			while(isdigit(s[i]))
			{
				num2+=s[i];	
				i++;
			}
			//数字转为字母 
			int n=std::stoi(num2),cnt=0;
			std::stack<char> st;
			while(n)
			{
				int x=n%26;
				char p;
				if(x==0) p='Z',n--;//26进制借位 
				else p='A'+x-1;
				st.push(p);
				n/=26;
			} 
			while(!st.empty()) 
			{
				std::cout<top();
				st.pop();
			}
			
			std::cout<'\n';
		}	
	}else{//开头不是R说明是字母数字型 
		std::string num;
		while(isdigit(s[i]))
		{
			num+=s[i];	
			i++;
		}
		//把字母转为数字 BC->55
		int ans=0;
		for(auto i:str)
		{
			ans=ans*26+i-'A'+1;	
		} 		 
		std::cout<<"R"<stoi(num)<<"C"<'\n';
	} 
}
signed main()
{
	int t; 
	std::cin>>t;
	while(t--)
	{
		solve();
	}
    return 0;
}

Dashboard - Educational Codeforces Round 157 (Rated for Div. 2) - Codeforces

题目大意：

给定n个字符串，字符串只含1-9。是否存在s=si+sj，使得s的前半部和等于后半部分和。（i和j可以相同）

对字符串的长度做标记。

然后枚举左串和右串的长度，判断是否偶数。

对所有符合条件的左串进行处理，将mid左边的和减去多余的右边，即该左串多出来的数，并记录。

再对所有右串进行处理，将mid右边的和减去多余的左边，即右串多出来的数sum，相应的需要左串缺少sum，即ans+=mp[-sum]。

#include
#define int long long
std::vector s[6];//标记字符串长度 
int ans;
signed main()
{
	int n;
	std::cin>>n;	
	n--;
	for(int i=1;i<=n;i++)
	{
		std::string x;
		std::cin>>x;
		s[x.size()].push_back(x);
	}
	for(int lenl=1;lenl<=5;lenl++)
	{
		for(int lenr=1;lenr<=5;lenr++)
		{
			std::map<int,int> mp;
			
			if((lenl+lenr)%2) continue;
			int mid=(lenl+lenr)/2;
			
			for(auto i:s[lenl])
			{
				int sum=0;
				for(int j=0;j
				{
					if(j
					{
						sum+=(i[j]-'0');	
					}else{
						sum-=(i[j]-'0');
					}		
				}	
				mp[sum]++;//左边多了sum 
			}
			
			for(auto i:s[lenr])
			{
				int sum=0;
				for(int j=0;j
				{
					if(j>=mid)
					{
						sum+=i[lenr-1-j]-'0';	
					} else{
						sum-=i[lenr-1-j]-'0';
					}
				}
				ans+=mp[-sum];
			}
		}
	}
	std::cout<
	return 0;
}