A-Shooting Game
题意：
三种球x,y,z分别值1,2,3。给出n种拿球方式和他的id，求价值最大的价值和她对应的id？
题解：知识点：贪心
签到题：就是求每种拿球方式总价值，然后把总价值拍一下序就行了，总价值就是x球个数1+y球个数2+z球个数*3；
代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
struct node {
ll a,b,c;
ll id;
ll sum;
}q[maxn];
bool cmp(node a,node b){
if(a.sum!=b.sum)return a.sum>b.sum;
else return a.id<b.id;
}
#define read read()
int main(){
sf("%lld",&n);
for(int i=1;i<=n;i++)
{
sf("%lld%lld%lld%lld",&q[i].id,&q[i].a,&q[i].b,&q[i].c);
q[i].sum=q[i].a+q[i].b*2+q[i].c*3;
}
sort(q+1,q+1+n,cmp);
pf("%lld %lld\n",q[1].id,q[1].sum);
return 0;
}
B-A Number.....
题意：给你一个整数y,和一个素数p，让你求是否有一个x使得（x*y）mod p = 1;如果这样的x存在，则输出x mod p;否则输出-1。
提示：对于任何整数a和正整数b，mod b是除以b的余数。提醒一下modb是非负的！
题解：知识点：扩展欧几里得
直接化成 yx+ p * b=1 解方程就行了，求x的值，
我们熟知的 是 ax+b*y=1 这种形式，
所以 其中y就是 a，b就是y ，p就是b，其实就是对应。这样不难想到扩展欧几里得，
就是最后要讨论一下 (y,p)是否互质，如果不互质，而且p为素数，所以最后， 取余之后 结果应该会是0或者y就是不是1，是1就互质了，所以是无解的。
代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y=y-a/b*x;
return d;
}
#define read read()
int main(){
sf("%lld",&t);
while(t--){
sf("%lld%lld",&n,&m);
ll x,y;
ll gcd=exgcd(n,m,x,y);
if(gcd==1){
//cout<<gcd<<endl;
sum=(x%m+m)%m;
pf("%lld\n",sum);
}
else cout<<-1<<endl;
}
return 0;
}
C-City Sup....
题意：n个城市，m条路，1为首都，求n个城市(除了1)到1的最短距离(有路就是两个城市就是1),成本是
求最小成本？结果取余1e9+7
题解：知识点：最短路
就是用最短路求出来各个点到1的最小距离，然后用快速幂求就行了别忘了取余，还有用long long。
代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e6+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=1e9+7;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,head[maxn],cnt,dist[maxn],vis[maxn];
struct wmy {
ll u,v,w,nx;
} a[maxn*4];
ll qpow(ll a,ll b){
ll sum=1;
while(b){
if(b&1) sum=sum*a%mod;
b>>=1;
a=a*a%mod;
}
return sum;
}
void add(ll u,ll v,ll w) {
a[cnt].u=u;
a[cnt].v=v;
a[cnt].w=w;
a[cnt].nx=head[u];
head[u]=cnt++;
}
#define read read()
int main(){
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1 ; i<=m ; i++) {
ll x, y;
sf("%lld%lld",&x,&y);
add(x,y,1);
add(y,x,1);
}
memset(dist,inf,sizeof(dist));
priority_queue<pii,vector<pii>, greater<pii> >q;
q.push({0,1});
dist[1]=0;
while(q.size()) {
pii fr=q.top();
q.pop();
ll dian=fr.second;
ll dis=fr.first;
for(int i=head[dian]; ~i; i=a[i].nx) {
ll e=a[i].v;
if(dist[e]>dis+a[i].w) {
dist[e]=dis+a[i].w;
q.push({dist[e],e});
}
}
}
ll ans=0;
for(int i=2 ; i<=n ; i++)
ans+=qpow(2,dist[i])%mod,ans%=mod;
cout<<ans<<endl;
return 0;
}
D-Moving.....
题意：就是给出你n个数，你的目的是让这n个数都相等你可以进行如下操作：选择一个数+(n-1)并且让其余(n-1)个数-1。当然这个(n-1)个数都是大于0的数。问是否能达到目的？
题解：知识点：优先队列
首先：如果判断这n个数平均数是否为整数，如果不是整数，再怎么变也达不到目的。
如果是整数：首先我们分析一下：我们要达到目的肯定是让小的加，大的减，这样我们那一个优先队列来维护队列中的最小值，因为是1+，多-，所以我们可以不断地测试最小的，如果最小的就是平均数就ok，
如果不是就不行，而且如果最小的小于零，也是不符合题意的。这样一想整体思路是通了。
但是你不能实现 (n-1)个同时-1呀，这样复杂度是过不去的，所以我们要把减的过程，改成O(1)的这样就可以过了，既然是(n-1)个同时减一我们是否可以看成{n个数同时减一，并且第一个数加n}这痒明显是可以的，当然这里第一个数是在变化的，他加上n之后的把+n之后的这个数入队，让队首元素出队，这样才能一个上队首一直维护最小值。然后我们用一个p变量来维护变幻的次数，也就是第一个应该减p测试。这样的话就成功的将复杂度降了下来，变成了O(1).
代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
/*priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
#define read read()
int main(){
t=read;
while(t--){
n=read;
while(!mn.empty())mn.pop();
sum=0;
for(int i=1;i<=n;i++){
a[i]=read;
sum+=a[i];
mn.push(a[i]);
}
if(sum%n!=0){
cout<<"No"<<endl;
}else {
p=sum/n;
ll nee=0;
flag=0;
for(int i=1;i<=10000;i++){
if(mn.top()-nee==p){flag=1;break;}
if(mn.top()-nee<0){flag=0;break;}
ll temp=mn.top()+n;//因为每一个都要减一所以最后让他 +n
mn.pop();
nee++;
mn.push(temp);
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}F-A Slimple Game
题意：
两个人玩游戏，给出一段字符串，你可以进行的操作有两种：
1，你可以把字符串中一个的'1'变成'0'。
2，你可以把字符串中连续的一段'0'，(知道两个)变成一个'1';
给出你n段，你可以同时操作多段，但是一段只能进行一种操作一次。问最后谁获胜。
题解：知识点：博弈论
我们首先通过这两种操作得知最后不能进行是一定是只有一个0，这样就无法进行了
先看一下'0','1'对结果的影响
字符串 操作数 加上一个0/操作数 加上两个0/操作数 加上3个0/操作成功数 ...... 1 1 10/3 100/3或者5 1000/3或者5或者7 ..... 11 4 110/4 1100/ 4或者6 11000/ 4或者6或者8 .... 111 5或者9 ... .... .... .... 1111 6或者10 ... ... ... ... ...
我们可以得到'1'的数量奇偶决定了操作数的奇偶。而且'0'对最后结果的就行没影响我们先看个栗子：
011和101和110 通过计算演变我们可以知道 这两个其实是等价的，都是可以6次。所以我们得知怎么排的对结果不造成任何影响。
我们再来看1110 我们可以知道他可以进行9次或者5次//x是操作数 x 字符串 1 1 1 0 1 0 1 1 0 2 0 0 1 0 3 0 0 0 0 4 1 0 0 5 1 1 6 0 1 7 0 0 8 1 9 0
或者
//x是操作数 x 字符串 1110 1 0110 2 0010 3 0000 4 1 5 0
结合上1.2.我们来看当操作数是奇数时：那就是到了(x表示第一个人，y表示第二个人) x完成最后一次 轮不到y所以x赢了。
在结合上1.2.3.我们看进行多组字符串的
进行可进行的操作数 每两次的变化 2 4 6 8 ->0 2 4 6 ->0 0 2 4->0 0 0 2->0 0 0 0 第二个人赢了 因为可以同时进行所以可以同时减 1 3 4-> 从上边推出偶数部分直接减去就可以了 最后也就是 1 1 0->第一个人开始使用->0 0 0所以就是第一个人赢 以2为一个周期，简单的说就是奇数的话只能是第一个人用 ，第二个人就不能进行操作了，所以第一个人就赢了。最后推推 其实也就是很简单了：就是统计每个字符串'1'得个数并判断奇偶，如果有一个是奇数那一定是第一个人赢，否则就是第二个人赢
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
#define read read()
int main(){
cin>>t;
while(t--){
cin>>n;
ans=0;
for(int i=1;i<=n;i++){
p=0;
cin>>str;
ll len=str.size();
for(int i=0;i<len;i++){
if(str[i]=='1')p++;
}
if(p%2==1) ans++;
}
if(ans!=0) cout<<"sdzNB"<<endl;
else cout<<"kgNB"<<endl;
}
return 0;
}G -Gaming with Mia
题意：给出你n个数这些数范围是(-1,0，1)你可以进行2种运算，一种*，另一种+，求结果最大是多少？
题解：知识点：DP
这个题无非就是一段乘积+一段乘积+一段乘积+...
/* 这样无非就是一段段乘积和 两个乘积是//这是不含零的 1*1//这个就用不到 -1*-1 -1*1//这个也用不到 1*-1//这个也用不到 三个乘积是 1*1*1//用不到 -1*-1*1//用不到 可以前两个相乘再加上1 -1*1*-1//这个可以用到 ..... 四个乘积 一定是2个-1 和两个1 -1*1*1*-1//可以用 1*-1*1*-1//用不到 -1*1*-1*1//用不到 -1*1*1*-1// 五个乘积我们就可以知道他可以转化成2+3或者1+4或者4+1或者3+2了 后面一样所以只讨论前4种就可以了。 ////0的话直接穿***去就行，并不影响我们的分析 */
代码：
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;
inline ll read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;*/
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[maxn][2];
string str,s;
#define read read()
int main(){
t=read;
while(t--){
n=read;
for(int i=1;i<=n;i++) a[i]=read,dp[i][0]=dp[i][1]=0;
dp[1][0]=a[1];
dp[1][1]=a[1];
for(int i=2;i<=n;i++){
l=a[i]*a[i-1];
ans=max(dp[i-2][1]+l,dp[i-2][0]+l);
dp[i][0]=max(dp[i][0],ans);//两个连乘
if(i>=3){
l=a[i]*a[i-1]*a[i-2];//三个连乘
ans=max(dp[i-3][1]+l,dp[i-3][0]+l);
dp[i][0]=max(dp[i][0],ans);
}
if(i>=4){
l=a[i]*a[i-1]*a[i-2]*a[i-3];//四个连乘
ans=max(dp[i-4][1]+l,dp[i-4][0]+l);
dp[i][0]=max(dp[i][0],ans);
}
dp[i][1]=max(dp[i][1],dp[i-1][1]+a[i]);
dp[i][1]=max(dp[i][1],dp[i-1][0]+a[i]);
}
cout<<max(dp[n][1],dp[n][0])<<endl;
}
return 0;
}
京公网安备 11010502036488号