A. PERFECT NUMBER PROBLEM
题目链接：https://nanti.jisuanke.com/t/38220
题意：
输出前五个完美数
分析：
签到。直接百度完美数输出即可
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define MOD 1000000007 #define INF 0x3f3f3f3f #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} const int N = 2e5 + 10; int main() { printf("6 28 496 8128 33550336 "); return 0; }
H. Coloring Game
题目链接：https://nanti.jisuanke.com/t/38227
题意：
给你个 2 * N 的网格 , 你有up(↑), down(↓), left(←), right(→), left up(↖), left down(↙), right up(↗), right down (↘) 八个路径走到下一个网格
网格原来是全白色的 , 你每经过一个网格它就会变黑色 （白变黑 , 黑变黑）. 要求你从左上角走到右下角 , 问能有多少种不同的配色方案（只要有一处网格颜色不同即为不同方案）
分析：
由于起点和终点固定 , 所以对于第一列和最后一列网格不同配色方案为 2 * 2 = 4 ; 而对于起点与终点之间的网格每一列都只有三种状态（黑白 、 白黑 、 黑黑）,所以答案为 4 * 3 ^ (n - 2) % MOD;
快速幂跑一遍。。。
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define INF 0x3f3f3f3f #define MOD 1000000007 #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} const int N = 2e5 + 10; int main() { ll n; cin >> n; if(n == 1){ cout << 1 << endl; return 0; } cout << 4 * pow_mod(3 , n - 2 , MOD) % MOD << endl; return 0; }
I. Max answer
题目链接：https://nanti.jisuanke.com/t/38228
题意：
给一个长为n(n <= 500000)的数组a, 对每个区间，求区间和乘区间最小值的最大值(−1e5 ≤ ai ≤1e5).
分析：
这道题乍一看像是单调栈的模板题 , 但很可惜的是 ai 的取值可以为负数 , 所以对于以 ai 为最小值的区间 , 若 ai 为负数 , 要找到最小区间和 , 若为 ai 为正数 , 要找到最大区间和
对于正数ai，利用单调栈寻找以ai为最小值的区间，利用前缀和数组求区间和再*ai 即结果（ai 为正数 , ai为区间最小值）
先用单调栈求出以a[i]为最小值能够延伸的左端点L[i]和右端点R[i] , 然后对于每个正数，我们用该数乘以这个区间和。区间和用前缀和来求，对于每个数所能影响的最大区间我们已经求出来了。对于负数来说，我们需要求在它右区间的最小前缀和减去左区间的最大前缀和 , 因为只有它的区间和最小对应的这个区间的value值才最大，又由区间和=sum[j]-sum[i]可知，sum[j]最小，sum[i]最大时才能时这个区间和最小，所以问题的关键转化为寻找最小的sum[j]和最大的sum[i]
对于右区间的最小前缀和，以及左区间的最大前缀和我们用线段树来求
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define MOD 1000000007 #define INF 0x3f3f3f3f #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} const int N = 5e5 + 10; ll sum[N],a[N]; ll maxn[N << 2],minn[N << 2]; void build(int l,int r,int root) { if(l==r) { maxn[root]=minn[root]=sum[l]; return ; } int mid=l+r>>1; build(l,mid,root<<1); build(mid+1,r,root<<1|1); maxn[root]=max(maxn[root<<1],maxn[root<<1|1]); minn[root]=min(minn[root<<1],minn[root<<1|1]); } ll qmax(int l,int r,int root,int ql,int qr) { if(l>=ql&&r<=qr) return maxn[root]; int mid=l+r>>1; ll ans=-INF; if(mid>=ql) ans=qmax(l,mid,root<<1,ql,qr); if(mid<qr) ans=max(ans,qmax(mid+1,r,root<<1|1,ql,qr)); return ans; } ll qmin(int l,int r,int root,int ql,int qr) { if(l>=ql&&r<=qr) return minn[root]; int mid=l+r>>1; ll ans=INF; if(mid>=ql) ans=qmin(l,mid,root<<1,ql,qr); if(mid<qr) ans=min(ans,qmin(mid+1,r,root<<1|1,ql,qr)); return ans; } int LL[N],RR[N],st[N]; int main() { ios; int n; cin >> n; rep(i ,1 ,n) cin >> a[i],sum[i] = sum[i-1]+a[i]; build(1,n,1); int top=0; rep(i ,1 ,n) { while(top&&a[st[top]]>a[i]) RR[st[top--]]=i-1; st[++top]=i; } while(top) RR[st[top--]]=n; for(int i=n;i>=1;i--) { while(top&&a[st[top]]>a[i]) LL[st[top--]]=i+1; st[++top]=i; } while(top) LL[st[top--]]=1; ll ans = -INF; rep(i ,1 ,n) { if(a[i]>0) ans=max(ans,a[i]*(sum[RR[i]]-sum[LL[i]-1])); else ans=max( ans,a[i]*( qmin(1,n,1,i,RR[i])-qmax(1,n,1,LL[i],i)) ); } cout << ans << endl; return 0; }
K. MORE XOR
题目链接：https://nanti.jisuanke.com/t/38230
题意：
分析：
对于 L - R 内的每一个数 ai 只有当 ai 出现次数为奇数时才会对结果做出贡献 , 所以我们可以先暴力打表找找规律
打表函数：
void f(int l,int r) { for(int i=l; i<=r; i++) cnt[i]++; } void g(int l,int r) { for(int x=l; x<=r; x++) for(int y=x; y<=r; y++) f(x,y); } void w(int l,int r) { for(int x=l; x<=r; x++) for(int y=x; y<=r; y++) g(x,y); }
记录每个数字出现的次数，奇数次说明这个数存在于答案中，偶数次相当于对答案没有贡献。打表找规律发现跟4的倍数有关，所以我们预处理以4为分组的异或和，然后O(1)输出结果就可以了。
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define MOD 1000000007 #define INF 0x3f3f3f3f #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} const int N = 1e5 + 10; ll a[N] , sum[N]; int n , q; int main() { int t; sd(t); while(t--) { cin >> n; rep(i ,1 ,n) sld(a[i]); sd(q); rep(i , 1 ,n) { if(i <= 4) sum[i] = a[i]; else sum[i] = sum[i - 4] ^ a[i]; } while(q--) { int l , r; sdd(l , r); int len = r - l + 1 ; ll ans ; if(len % 4 == 0) ans = 0; else if(len % 4 == 1) { ans = sum[r]; if(l - 4 > 0) ans ^= sum[l - 4]; } else if(len % 4 == 2) { ans = sum[r] ^ sum[r - 1]; if(l - 3 > 0) ans ^= sum[l - 3]; if(l - 4 > 0) ans ^= sum[l - 4]; } else if(len % 4 == 3) { ans = sum[r - 1]; if(l - 3 > 0) ans ^= sum[l - 3]; } pld(ans); } } return 0; }
M. Subsequence
题目链接：https://nanti.jisuanke.com/t/38232
题意：
给你个母串S , 在给你 N 个字符串 T , 为 T 是否为 S 的子序列
分析：
这道题时间卡得有点过分 , 我用 string 读取字符串竟然分分钟 Tle 。。。
首先我们用 nex[ i ][ j ] 表示 S 串中 i 字符之后的离它最近的 j 字符的位置 , 从后往前预处理 S串中每一个字符 i 的下一位字符 j 的位置
然后输入 T 串判断 T 串当前字符 now1和 T 串下一个字符 T[i] 在主串中的位置是否会合法（即判断nex[now1][ T[i] - 'a'] 是否会小于 len（字符串下标从0开始） ）
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define INF 0x3f3f3f3f #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; template<typename T>void read(T &res) { bool flag=false; char ch; while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm; isdigit(ch=getchar()); res=(res<<1)+(res<<3)+numm); flag&&(res=-res); } template<typename T>void Out(T x) { if(x<0)putchar('-'),x=-x; if(x>9)Out(x/10); putchar(x%10+'0'); } ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll lcm(ll a,ll b) { return a*b/gcd(a,b); } ll pow_mod(ll x,ll n,ll mod) { ll res=1; while(n) { if(n&1)res=res*x%mod; x=x*x%mod; n>>=1; } return res; } ll fact_pow(ll n,ll p) { ll res=0; while(n) { n/=p; res+=n; } return res; } const int N = 1e5 + 10; int nex[N][30]; int now[N]; char s[N] , t[N]; void init(int &len) { len = strlen(s); rep(i , 0 , len - 1) now[i] = len; for(int i = len - 1 ; i >= 0 ; i --) { for(int j = 0 ; j < 26 ;j ++) { nex[i][j] = now[j]; } now[s[i] - 'a'] = i; } } int main() { scanf("%s" , s); int len ; init(len); int n; read(n); while(n --) { scanf("%s" , t); int len2 = strlen(t); int flag = 0; int now1 = now[t[0] - 'a']; if(len < len2) { puts("NO"); continue; } if(now1 >= len) { puts("NO"); continue; } for(int i = 1 ; i < len2 ; i++) { now1 = nex[now1][t[i] - 'a']; if(now1 >= len){flag = 1 ;break;} } if(flag) puts("NO"); else puts("YES");/*123*/ } return 0; }