牛客多校4

牛客多校4

L

思路

问题:

写的时候主要困扰的问题有两个

1. 怎么处理操作

​ 按正常顺序操作的话,我们需要得知操作当前 行或者列会亮了多少个灯,因为数据范围很大,是不可能每次都循环列数或者行数的.

2.计算数量

​ 对于行数来说,就是看之前有多少列开灯了

​ 对于列数来说,就是看之前有多少行开灯了

​ 但是因为第一个问题难以处理导致我们很难快速得到相关数据.

我们每次操作后我们都需要重新维护数据,导致我们无法快速算出答案

解决:

我们灯的状态都是以对他最后一次操作为基准的,即无论前面进行了这样的操作,灯的状态都是以最后一次操作相关.

因此当我们知道他的最后一次状态是什么样时,就就不需要管他之前的操作了.

因此我们从最后一次操作往前推的话,就可以得到任一行或者一列的最后状态,然后对于已经确定的状态不在理会

对还未确定的状态计算其可以开的灯的数量就可以了.

在计算时,依旧可以用上面的方式计算.

• 当操作列数开灯时,我们知道已经知道了最后有多少行数操作,即多少个灯的状态已经被确定了,那么我们的操作开的就是剩下的灯了.
• 行上开灯操作也是同理.

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int n,m,q;
const int N = 1000010;
int r[N];
int c[N];
int numr;
int numc;
struct node
{
	string s1;
	int x;
	string s2;
}nodes[N];
int main()
{
	 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	 cin>>n>>m>>q;
	 for(int i = 1;i<=q;i++)
	 {
	 	string s1;
	 	string s2;
	 	int x;
	 	cin>>s1>>x>>s2;
	 	nodes[i] = {s1,x,s2};
	 }
	 ll sum =0;
	 for(int i = q;i;i--)
	 {
	 	string str1 = nodes[i].s1;
	 	int  x = nodes[i].x;
	 	string str2 = nodes[i].s2;
	 	if(str1=="row")
	 	{
	 		if(r[x]) continue;
	 		else
	 		{
	 			if(str2=="on")
	 			{
	 			    sum+= (m - numc);
	 			}
	 			r[x] = 1;
	 			numr++;
	 		}
	 	}
	 	else
	 	{
	 		if(c[x]) continue;
	 		else
	 		{
	 			if(str2=="on")
	 			{
	 				 sum+=(n - numr);
	 			}
	 			c[x] = 1;
	 			numc++;
	 		}
	 	}
	 }
	 cout<<sum<<"\n";
	 return 0;
}

A

思路

s全为0或者全为1

• 当t全为1或者0时我们反着构造就可以了;

• 当t, 01混杂时, 假如s全为1或0,那么s本身不可能出现t

  证明

所以我们只要枚举全1或者全0再判断就可以了

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
string s,t;
int T,n;
void solve(){
    cin>>n>>t;
    string s1(n,'1');
    int cnt=0;
    s=t+s1+t;
    int pos=0;
    while((pos=s.find(t,pos))!=string::npos)
    {pos++;cnt++;}
    if(cnt==2) cout<<s1<<endl;
    else       cout<<string(n,'0')<<endl;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)solve();
    return 0;
}