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; } }