河南理工大学新入生挑戦試合

ここをクリックしてテーマを見ることができますよ!A.水題~サイン
B.The flower題意:文字列を1つ与え、文字列からサブストリングを得、サブストリングが状況を満たすことを意味する.出現回数が2より大きい.2.サブストリングの長さはkに等しい.このような列がいくつあるかを見つけて辞書順に印刷します
構想:mapメモリのサブストリングで数を計算し、setで並べ替え、文字列を切り取るときは長さを直接横切ってサブストリングを切り取ることができないことに注意しなければならない.切り取り長さが分からないからだ.だからi=k-1から始めます.それからサブストリングを遍歴して、mapの中のどれが>2なのかを見て、それからこのサブストリングを新しいset容器の中に挿入して、目的は並べ替えて、それから大きさを出力して、出力サブストリングを遍歴すればいいです!

#include

using namespace std;

int main(){
	string s;
	int k;
	cin>>s>>k;
	unordered_map<string,int> mmp;
	set<string> st;
	int n = (int)s.length();
	for(int i = k-1;i<n;i++){
	  string now = s.substr(i-(k-1),k);
	  mmp[now]++;
	  st.insert(now);
	  }
	  set<string> ans;
	  for(auto v:st){
	  	if(mmp[v]>2)
	  	  ans.insert(v);
	  }
	  cout<<(int)ans.size()<<endl;
	  for(auto v:ans) cout<<v<<endl;
	  return 0;
}

C.タイトルリンク

#include
 
using namespace std;
const int N = 1e6+100;
vector<int> G[N];
int pre[N],a[N],par[N];
long long bit[30];
int f[N][30];
int depth[N];
void init(){
	bit[0]=1;
	for(int i=1;i<=29;i++) bit[i]=(bit[i-1]<<1);
}
void dfs(int u,int par){
	depth[u]=depth[par]+1;
	f[u][0]=par;
	for(int i=1;bit[i]<=depth[u];i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int v:G[u]){
		if(v!=par) dfs(v,u);
	}
}
int lca(int x,int y){
	if(depth[x]<depth[y]) swap(x,y);
	for(int i=29;i>=0;i--){
		if(depth[x]-depth[y]>=bit[i]){
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=29;i>=0;i--){
		if(depth[x]>=(1<<i)&&f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
void DFS1(int u,int fa){
    par[u]=fa;
    pre[u]=pre[fa]^a[u];
    for(int v:G[u]){
        if(v==fa) continue;
        DFS1(v,u);
    }
}
int main(){
    int n,u,v,q;
    cin>>n;
    init();
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=n;i++) G[i].clear();
    for(int i=1;i<=n-1;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    DFS1(1,0);
    int x,y;
    cin>>q;
    while(q--){
        cin>>x>>y;
        int c=lca(x,y);
        int f=par[c];
        cout<<(pre[x]^pre[f]^pre[c]^pre[y])<<endl;
    }
    return 0;
}

D.LaunchPad題意:長方形のランプで、ランダムな四角形をクリックすると、この四角形に対応する列と行が変化し、明るく暗くなったり、暗くなったりします.Q回の操作を経てどれだけの明かりが点灯しているかを聞く.
考え方:この問題の暴力は私がやってみないで、その操作過程を模擬します.そしてタイムアウトです.2つの1次元配列で行または列に変化があるかどうかを表し、1つの2次元配列でランプの動作後の明るさの変化を表すように最適化しなければなりません.行と列の調整に使用されるアクションです.

#include
using namespace std;
#define ll long long
const int maxn=1000+10;

int a[maxn],b[maxn];

int c[maxn][maxn];

int main()
{
	int n,m,q;
	cin>>n>>m;
	cin>>q;
	while(q--){
		int u,v;
		cin>>u>>v;
		c[u][v]^=1;
		a[u]^=1;
		b[v]^=1;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans+=a[i]^b[j]^c[i][j];
		}
	}
	cout<<ans<<endl;
    return 0;
}

E.水~~题意:一番长い文字列を见つけることでしょう
考え方:少し欲張りな味がして、よく観察すると、長さが2のすべての状況があります.3もそうです.だから一番長くするには、一番短くすればいいので、文字列の長さを2で割るといいです!

#include

using namespace std;

int main(){
	int n;
	cin>>n;
	while(n--){
		string s;
	cin>>s;
	int l = s.length();
	cout<<l/2<<endl;
	}
	
	return 0;
} 

F.題意:数字の中の輪の数を見せることです.
考え方:~~

#include
using namespace std;

int main()
{
    int t;
	cin>>t;
	while(t--){
		string s;
		cin>>s;
		int l = s.length();
		int num = 0;
		for(int i =0;i<l;i++){
			if(s[i] == '0') num++;
			if(s[i] == '4') num++;
			if(s[i] == '6') num++;
			if(s[i] == '8') num+=2;
			if(s[i] == '9') num++;
		}
		cout<<num<<endl;
	} 
    return 0;
}

G.題意はあなたにたくさんの規則をあげて、1 E 9+7に対してmodの結果を取ることを求めさせます.考え方:上の小さな三角形は楊輝三角で、下の小さな三角形は楊輝三角で、別々に見ればいいです.

#include
using namespace std;
#define ll long long
const ll mod=1e9+7;
const int maxn=100000+10;
ll fac[maxn];

ll pow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

ll solve(int n,int m){
	n--;
	if(m%2==0) n--;
	m=(m-1)/2;
	printf("%lld
",fac[n]*pow(fac[m],mod-2)%mod*pow(fac[n-m],mod-2)%mod);
}
int main()
{
	int t,n,m;
	scanf("%d",&t);
	fac[0]=1;
	for(int i=1;i<=maxn;i++) fac[i]=fac[i-1]*i%mod;
	while(t--){
		scanf("%d %d",&n,&m);
		solve(n,m);
	}
	return 0;
}

H.

#include
using namespace std;
#define ll long long
const int maxn=1000000+10;

const ll mod=1e9+7;

ll T,n;


ll qp(ll a,ll b){//     
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

//     x        1 
ll judge(ll x){
	ll sum=(qp(4,x)-1+mod)%mod;
	return 2*sum*qp(3,mod-2)%mod;
}
//      
ll bits(ll x){
	ll sum=0;
	while(x){
		sum++;
		x>>=1;
	}
	return sum;
}
ll revise(ll x,ll step){
	ll pos=1;
	stack<ll>st;
	for(int i=1;i<=step;i++){
		if(i%2==0) st.push(1-(x&1));
		else st.push(x&1);
		x>>=1;
	}
	ll sum=0;
	while(!st.empty()){
		sum=sum*2+st.top();
		st.pop();
	}
	return sum;
}

int main()
{
	cin>>T;
	while(T--){
		ll res;
		cin>>n;
		if(n&1){
			ll vis=bits(n);
			//          
			res=judge((n-vis)/2);
			if((n-vis)&1) res=(res*2+1)%mod;
			res=res*qp(2,vis)%mod;
			//       
			res=(res+revise((1ll<<vis)-n,vis))%mod;
			
			//     or  
			if((n/2)&1){
				if(n&1) res=(res-1+mod)%mod;
				else res=(res+1)%mod;
			}
		}
		else{
			res=judge(n/2);
			if((n/2)&1) res=(res+1)%mod;
		}
		cout<<res<<endl;
	}
	return 0;
}

I.題意:バイナリに変換してcopy n(十進法)回を乗じる.中に110がいくつあるか見てください.
構想:すなわち,各0の寄与を求めるために,ある0の前にn個の1があれば,その寄与はa∗(a−1)/2である.

#include
#define ll long long 
using namespace std;

const ll mod = 1e9+7;

int q[123];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
        
		ll num=0;
		ll ans = 0;
		ll x = n;
        
		while(x){//      ，    
			q[num++] = x&1;
			x>>=1;
		}
		//for(int i=0;i
		 //cout<
		
		x = 0;
		for(int i=0;i<n;i++){//   
			for(int j=num-1;j>=0;j--){
				if(q[j]) x++;
				else
				 ans = (ans+x*(x-1)/2)%mod;
			}
		}
		cout<<ans<<endl;
	}
}

K

#include
using namespace std;
const int maxn=2000000+10;

char s[maxn],t[maxn];

int main()
{
    int n;
    cin>>n; 
    cin>>s>>t;
    int a=0,b=0;
    for(int i=0;i<n;i++){
        if(s[i]=='-') a++;
        else a--;
        if(t[i]=='-') b++;
        else b--;
    }
    
    int prea,preb;
    prea=a+max(1-min(a,b),0);
    preb=b+max(1-min(a,b),0);
 
    printf("%d %d
",0,prea+preb+n*2);
 
    printf("%d",prea);
    for(int i=1;i<=n;i++) printf(" %d",1);
    printf("
");
 
    printf("%d",preb);
    for(int i=1;i<=n;i++) printf(" %d",1);
    printf("
");

    return 0;
}