A 小月的模块

签到

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define endl "\n"
#define pb push_back
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define int long long
typedef pair<int,int> PII;


const int N=200;
int n,k,s;
int a[N]; 
 
void solve()
{
	cin>>n>>k>>s;
	if(n==0)cout<<k;
	else cout<<s;
	
}
signed main()
{
	IOS
	int T=1;//cin>>T;
	while(T--) solve();
	return 0;
}

B 小月的信号

一直除以2，记录第一个和最后一个1，和1的个数

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define endl "\n"
#define pb push_back
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define int long long
typedef pair<int,int> PII;


const int N=200;
int n,sum,mx,mi;
int a[N]; 
 
void solve()
{
	cin>>n;
	sum=0;mx=mi=-1;
	int cnt=0;
    while(n){
    	if(n%2){
    		if(mi==-1)mi=cnt;
    		mx=cnt;
    	   sum++;	
		}
		n/=2;
		cnt++;
	}
	cout<<sum<<" "<<mi<<' '<<mx;
}
signed main()
{
	IOS
	int T=1;//cin>>T;
	while(T--) solve();
	return 0;
}

C 小月的灯带

前缀和数组，二分查找所在区间

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define endl "\n"
#define pb push_back
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define int long long
typedef pair<int,int> PII;


const int N=200100;
int n,q,b;
int a[N]; 
 
void solve()
{
	cin>>n>>q>>b;a[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=a[i-1];
	}
	while(q--){
		int tp;
		cin>>tp;
		int cnt=lower_bound(a+1,a+n+1,tp)-a;
		if(b){
			if(cnt%2)cout<<1<<" "<<cnt<<" "<<tp-a[cnt-1];
			else cout<<0<<" "<<cnt<<" "<<tp-a[cnt-1];
		}
		else{
			if(cnt%2==0)cout<<1<<" "<<cnt<<" "<<tp-a[cnt-1];
			else cout<<0<<" "<<cnt<<" "<<tp-a[cnt-1];
		}
		cout<<endl;
	}
}
signed main()
{
	IOS
	int T=1;//cin>>T;
	while(T--) solve();
	return 0;
}

D 小月的校验码

存入unordered_map，枚举每一种情况，通过ump查找

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define endl "\n"
#define pb push_back
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define int long long
typedef pair<int,int> PII;


const int N=200100;
int n,m;
string a[N]; 
int num[N];
unordered_map<string,int>mp;
 
void solve()
{
	cin>>n>>m;
	memset(num,0,sizeof(num));
	int sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]=i;
		for(int j=1;j<=m;i++){
			string tp=a[j];
			if(tp[j]=='1')tp[j]='0';
			else tp[j]='1';
			auto it = mp.find(tp);
            if(it != mp.end()){
            	sum++;
                num[j]++;
            }
		}
	}
	cout<<sum<<endl;
	for(int i=1;i<=m;i++){
		cout<<num[i]<<' ';
	}
}
signed main()
{
	IOS
	int T=1;//cin>>T;
	while(T--) solve();
	return 0;
}

E 小月的前缀集合

通过ump模拟整个过程

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define endl "\n"
#define pb push_back
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define int long long
typedef pair<int,int> PII;

const int N=200100;
int n,sum;
string a[N];
unordered_map<string,int>mp;

void in(string s){
    int l=s.length();
    for(int i=1;i<=l;i++){
        string tp = s.substr(0,i);
        auto it = mp.find(tp);
        if(it != mp.end()){
            int tmp=it->second;
            mp[tp]=tmp+1;
        }else{
            sum++;
            mp[tp]=1;
        }
    }
}

void out(string s){
    int l=s.length();
    for(int i=1;i<=l;i++){
        string tp = s.substr(0,i);
        auto it = mp.find(tp);
        if(it != mp.end()){
            int tmp=it->second;
            if(tmp == 1){
                sum--;
                mp.erase(it);
            }else{
                mp[tp]=tmp-1;
            }
        }
    }
}

void solve()
{
    cin>>n;
    mp.clear();
    sum = 0;

    for(int i=1;i<=n;i++){
        char op;
        cin>>op>>a[i];
        if(op == '+') in(a[i]);
        else out(a[i]);
        cout<<sum<<endl;
    }
}

signed main()
{
    IOS
    int T=1;
    while(T--) solve();
    return 0;
}

F 小月的路径码

树上差分、欧拉序、树状数组

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define endl "\n"
#define pb push_back
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define int long long
typedef pair<int,int> PII;

const int N=200100;
const int MOD=1e9+7;
int n,q;
string s;

int szsz[N];
int quan[N];

vector<vector<int>> graph;

int dfn[N];
int rt[N];
int h[N];//深度

int cc=1;

void Add(int x,int v){
	while(x<=n){
		szsz[x]+=v;
		x+=x&-x;
	}
}

int Pre(int x){
	int res=0;
	while(x){
		res+=szsz[x];
		x&=x-1;
	}
	return res;
}

void DFS(int x,int fa){
	dfn[x]=cc;
	cc++;
	for(const auto& y:graph[x]){
		if(y!=fa){
			h[y]=h[x]+1;
			DFS(y,x);
		}
	}
	rt[x]=cc;
	if(s[x]=='1'){
		Add(dfn[x],quan[h[x]]);
		Add(cc,-quan[h[x]]);
	}
}

void solve()
{
	cin>>n>>q>>s;
	s=' '+s;
	graph.resize(n+1);
	
	//存图
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	
	//预处理权值
	quan[0]=1;
	for(int i=1;i<=n;i++){
		quan[i]=quan[i-1]<<1;
		if(quan[i]>=MOD){
			quan[i]-=MOD;
		}
	}
	
	DFS(1,0);
	while(q--){
		int u;
		char op;
		cin>>op>>u;
		if(op=='F'){
			if(s[u]=='0'){
				Add(dfn[u],quan[h[u]]);
				Add(rt[u],-quan[h[u]]);
				s[u]='1';
			}
			else{
				Add(dfn[u],-quan[h[u]]);
				Add(rt[u],quan[h[u]]);
				s[u]='0';
			}
			continue;
		}
		cout<<Pre(dfn[u])%MOD<<endl;
	}
}

signed main()
{
	IOS
	int T=1;
	while(T--) solve();
	return 0;
}