首页 技术 正文
技术 2022年11月19日
0 收藏 793 点赞 4,510 浏览 11933 个字

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", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", 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<<)+(res<<)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
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=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}const int N = 2e5 + ;int main()
{
printf("6\n28\n496\n8128\n33550336\n");
return ;
}

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", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", 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<<)+(res<<)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
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=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}const int N = 2e5 + ;int main()
{
ll n;
cin >> n;
if(n == ){
cout << << endl;
return ;
}
cout << * pow_mod( , n - , MOD) % MOD << endl;
return ;
}

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", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", 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<<)+(res<<)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
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=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}const int N = 5e5 + ;
ll sum[N],a[N];
ll maxn[N << ],minn[N << ];
void build(int l,int r,int root)
{
if(l==r)
{
maxn[root]=minn[root]=sum[l];
return ;
}
int mid=l+r>>;
build(l,mid,root<<);
build(mid+,r,root<<|);
maxn[root]=max(maxn[root<<],maxn[root<<|]);
minn[root]=min(minn[root<<],minn[root<<|]);
}
ll qmax(int l,int r,int root,int ql,int qr)
{
if(l>=ql&&r<=qr)
return maxn[root];
int mid=l+r>>;
ll ans=-INF;
if(mid>=ql)
ans=qmax(l,mid,root<<,ql,qr);
if(mid<qr)
ans=max(ans,qmax(mid+,r,root<<|,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>>;
ll ans=INF;
if(mid>=ql)
ans=qmin(l,mid,root<<,ql,qr);
if(mid<qr)
ans=min(ans,qmin(mid+,r,root<<|,ql,qr));
return ans;
}
int LL[N],RR[N],st[N];
int main()
{
ios;
int n;
cin >> n;
rep(i , ,n)
cin >> a[i],sum[i] = sum[i-]+a[i];
build(,n,);
int top=;
rep(i , ,n)
{
while(top&&a[st[top]]>a[i])
RR[st[top--]]=i-;
st[++top]=i;
}
while(top)
RR[st[top--]]=n;
for(int i=n;i>=;i--)
{
while(top&&a[st[top]]>a[i])
LL[st[top--]]=i+;
st[++top]=i;
}
while(top)
LL[st[top--]]=;
ll ans = -INF;
rep(i , ,n)
{
if(a[i]>)
ans=max(ans,a[i]*(sum[RR[i]]-sum[LL[i]-]));
else
ans=max( ans,a[i]*( qmin(,n,,i,RR[i])-qmax(,n,,LL[i],i)) );
}
cout << ans << endl;
return ;
}

K. MORE XOR

题目链接:https://nanti.jisuanke.com/t/38230

题意:

2019 The Preliminary Contest for ICPC China Nanchang National Invitational(A 、H 、I 、K 、M)

分析:

对于 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", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", 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<<)+(res<<)+numm);flag&&(res=-res);}
template<typename T>void Out(T x){if(x<)putchar('-'),x=-x;if(x>)Out(x/);putchar(x%+'');}
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=;while(n){if(n&)res=res*x%mod;x=x*x%mod;n>>=;}return res;}
ll fact_pow(ll n,ll p){ll res=;while(n){n/=p;res+=n;}return res;}const int N = 1e5 + ;ll a[N] , sum[N];
int n , q;
int main()
{
int t;
sd(t);
while(t--)
{
cin >> n;
rep(i , ,n)
sld(a[i]);
sd(q);
rep(i , ,n)
{
if(i <= ) sum[i] = a[i];
else
sum[i] = sum[i - ] ^ a[i];
}
while(q--)
{
int l , r;
sdd(l , r);
int len = r - l + ;
ll ans ;
if(len % == )
ans = ; else if(len % == )
{
ans = sum[r];
if(l - > )
ans ^= sum[l - ];
} else if(len % == )
{
ans = sum[r] ^ sum[r - ];
if(l - > )
ans ^= sum[l - ];
if(l - > )
ans ^= sum[l - ];
} else if(len % == )
{
ans = sum[r - ];
if(l - > )
ans ^= sum[l - ];
}
pld(ans);
}
}
return ;
}

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", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", 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<<)+(res<<)+numm);
flag&&(res=-res);
}
template<typename T>void Out(T x)
{
if(x<)putchar('-'),x=-x;
if(x>)Out(x/);
putchar(x%+'');
}
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=;
while(n)
{
if(n&)res=res*x%mod;
x=x*x%mod;
n>>=;
}
return res;
}
ll fact_pow(ll n,ll p)
{
ll res=;
while(n)
{
n/=p;
res+=n;
}
return res;
}
const int N = 1e5 + ;
int nex[N][];
int now[N];
char s[N] , t[N];
void init(int &len)
{
len = strlen(s);
rep(i , , len - ) now[i] = len;
for(int i = len - ; i >= ; i --)
{
for(int j = ; j < ;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 = ;
int now1 = now[t[] - 'a'];
if(len < len2)
{
puts("NO");
continue;
}
if(now1 >= len)
{
puts("NO");
continue;
}
for(int i = ; i < len2 ; i++)
{
now1 = nex[now1][t[i] - 'a'];
if(now1 >= len){flag = ;break;}
}
if(flag) puts("NO");
else puts("YES");/**/
}
return ;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,085
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,560
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,409
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,182
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,819
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,902