A.Rikka with Lowbit
这题深深的让我感觉到了什么叫毒里有水,这题属实教会了我什么是lowbit,研究了半天lowbit发现其实不用研究,难绷了属于是,试了几组数据发现x不管经过多少次f(x)最后的期望还是x,于是操作1就可以直接无视掉了,如果是操作2就直接输出一下就好了,所以就把前面的加起来就好了,不过这么写肯定是会超时的,于是需要用到前缀和,再乘以2^nm,这里则需要用到快速幂算法,log2n次得到答案,当然由于数字巨大,每一步都不能忘掉取模。
知识点:前缀和,快速幂
#include<bits/stdc++.h>
using namespace std;
long long mod=998244353;
int main()
{
int t;
cin>>t;
while(t--)
{
long long n,m;
long long a[100010]={0};
cin>>n>>m;
long long v=n*m,c=2,s=1;
while(v)
{
if(v&1)
s=(s*c)%mod;
c=(c*c)%mod;
v/=2;
}
for(long long i=1;i<=n;i++)
{
cin>>a[i];
a[i]=(a[i]+a[i-1])%mod;
}
long long f,l,r;
while(m--)
{
cin>>f>>l>>r;
if(f==2)
cout<<((((a[r]-a[l-1])%mod)*s)%mod+mod)%mod<<endl;
}
}
}
J.Rikka with Nickname
更水的一题,题目的意思是给几个字符串,如果有相同的即可拼再一起当消消乐玩,直接暴力搜索o(10^6)即可解决
知识点:字符串处理和暴力算知识点吗()
下附代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
for(int i=1;i<n;i++)
{
string t;
cin>>t;
int k=0,p=0;
while(k<s.size())
{
if(s[k++]==t[p])
p++;
if(p==t.size())
break;
}
for(int j=p;j<t.size();j++)
s+=t[j];
}
cout<<s<<endl;
}
}

京公网安备 11010502036488号