河南理工大学新生挑战赛
点击这里可以查看题目哦！ A.水题~签到
B.The flower 题意：意思就是给一个字符串，然后从字符串中得到子串，并且子串满足情况 1.出现次数大于2,； 2.子串的长度等于k； 找到有多少个这样的串然后按照字典序打印出来
思路：用map存子串用来计算数目，然后用set来去重并排序，在截取字符串的时候要注意不能直接遍历长度截取子串，因为截取长度不知。所以要从i = k-1开始。然后就是遍历子串，看map里面哪一个>2,然后把这个子串插入到一个新的set容器里面，目的是排序，然后输出大小，遍历输出子串即可！
#include<bits/stdc++.h>
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<bits/stdc++.h>
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次操作后有多少灯是亮着的。
思路：这个题暴力我试着过不去，就是模拟其操作过程。然后是超时。 我们得试着优化，用两个一维数组来表示行或者列是否有变化，用一个二维数组来表示灯在操作后的亮暗变化。用来调整行和列所带来的的一次操作。
#include<bits/stdc++.h>
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<bits/stdc++.h>
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<bits/stdc++.h>
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.题意就是给你一堆规则，让你求一个数对1E9+7取mod的结果。 思路：向上的小三角形是一个杨辉三角，向下的小三角形是一个杨辉三角，分开看就行了。
#include<bits/stdc++.h>
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\n",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<bits/stdc++.h>
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<bits/stdc++.h>
#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<num;i++)
//cout<<q[i]<<endl;
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<bits/stdc++.h>
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\n",0,prea+preb+n*2);
printf("%d",prea);
for(int i=1;i<=n;i++) printf(" %d",1);
printf("\n");
printf("%d",preb);
for(int i=1;i<=n;i++) printf(" %d",1);
printf("\n");
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-01-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读