B - Magical Subsequence
题目链接B - Magical Subsequence
#include<bits/stdc++.h>
#define mst(s,x) memset(s,x,sizeof(s));
#define sr(x) scanf("%d",&x);
#define sr2(a,b) scanf("%d%d",&a,&b);
#define sr3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define sr3d(a,b,c) scanf("%lf%lf%lf",&a,&b,&c);
#define sr4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d);
#define f(i,a,n) for(int i=a;i<=n;i++)
#define sc(x) cout<<#x<<" : "<<x<<endl;
#define hh cout<<endl;
#define dd double
#define inf 1e18
#define ll __int128
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return w==1?x:-x;
}
inline void write(ll x)
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
const int N=1e5+5;
int n,maxn;
int a[N];
int flag[N];
int check(int x)
{
int ans=0,cnt=1;
mst(flag,0);
f(i,1,n)
{
if(a[i]>=x)continue;
if(flag[x-a[i]]==cnt)ans++,cnt++;
else flag[a[i]]=cnt;
}
return ans*2;
}
void solve()
{
sr(n);
f(i,1,n)sr(a[i]);
f(i,2,200)maxn=max(maxn,check(i));
printf("%d",maxn);
}
signed main()
{
int T=1;
for(int i=1;i<=T;i++)
{
solve();
}
return 0;
}
D-Math-master
题目链接D-Math-master
#include<bits/stdc++.h>
#define mst(s,x) memset(s,x,sizeof(s));
#define sr(x) scanf("%d",&x);
#define sr2(a,b) scanf("%d%d",&a,&b);
#define sr3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define sr3d(a,b,c) scanf("%lf%lf%lf",&a,&b,&c);
#define sr4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d);
#define f(i,a,n) for(int i=a;i<=n;i++)
#define sc(x) cout<<#x<<" : "<<x<<endl;
#define hh cout<<endl;
#define dd double
#define inf 1e18
#define ll __int128
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return w==1?x:-x;
}
inline void write(ll x)
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
const int N=1e3+5;
ll a,b;
int A[N],B[N];
int la,lb;
string sa,sb;
ll aa,bb;
int jcntb[20],jcnta[20];
bool check2(int x)
{
aa=0;
for(int i=0;i<10;i++)jcntb[i]=0,jcnta[i]=0;
for(int i=0;i<sa.size();i++)
{
if(x&(1<<i))aa=aa*10+sa[i]-'0';
else jcnta[sa[i]-'0']++;
}
if(aa==0) return false;
bb=aa*b/a;
if(bb*a!=aa*b) return false;
ll tb=bb;
for(int i=1;i<=lb;i++)
{
if(tb==0&&B[i]==0)continue;
if(tb%10==B[i])tb/=10;
else jcntb[B[i]]++;
}
for(int i=0;i<=9;i++)if(jcnta[i]!=jcntb[i])return false;
return true;
}
void solve()
{
a=read(),b=read();
ll na=a,nb=b;
sa=sb="";
la=lb=0;
while(na)A[++la]=na%10,na/=10;
while(nb)B[++lb]=nb%10,nb/=10;
for(int i=la;i>=1;i--)sa+=(char)A[i]+'0';
for(int i=lb;i>=1;i--)sb+=(char)B[i]+'0';
ll temp=(1<<la)-1;
ll ansa=a,ansb=b;
for(int i=0;i<=temp;i++)
{
if(check2(i)&&ansa>aa) ansa=aa,ansb=bb;
}
write(ansa);
printf(" ");
write(ansb);
hh
}
signed main()
{
int T=1;
cin>>T;
for(int i=1;i<=T;i++)
{
solve();
}
return 0;
}
E - Power and Modulo
题目链接E - Power and Modulo
#include<bits/stdc++.h>
#define mst(s,x) memset(s,x,sizeof(s));
#define sr(x) scanf("%d",&x);
#define sr2(a,b) scanf("%d%d",&a,&b);
#define sr3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define sr3d(a,b,c) scanf("%lf%lf%lf",&a,&b,&c);
#define sr4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d);
#define f(i,a,n) for(int i=a;i<=n;i++)
#define ff(i) for(int i=1;i<=n;i++)
#define sc(x) cout<<#x<<" : "<<x<<endl;
#define hh cout<<endl;
#define dd double
#define inf 0x3f3f3f3f
#define ll __int128
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return w==1?x:-x;
}
inline void write(ll x)
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
const int N=1e5+5;
int n;
int a[N];
inline void solve()
{
sr(n);
ff(i)sr(a[i]);
int flag=0;
int mod=0;
int wz=0;
ff(i)
{
if(a[i]<1<<(i-1))
{
flag=1;
mod=(1<<(i-1))-a[i];
wz=i;
break;
}
else if(a[i]>1<<(i-1))
{
puts("-1");
return;
}
}
if(!flag)
{
puts("-1");
return;
}
f(i,wz,n)
{
if(a[i]!=a[i-1]*2%mod)
{
puts("-1");
return;
}
}
printf("%d\n",mod);
}
signed main()
{
int T=1;
cin>>T;
for(int i=1;i<=T;i++)
{
solve();
}
return 0;
}
G - Damaged Bicycle
题目链接G - Damaged Bicycle
（稍作说明
链式前向星的N要开大点不然会WA掉 1e5就寄了
不用堆优化dijk会T掉
不用状压会M
#include<bits/stdc++.h>
#define mst(s,x) memset(s,x,sizeof(s));
#define sr(x) scanf("%d",&x);
#define sr2(a,b) scanf("%d%d",&a,&b);
#define sr3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define sr3d(a,b,c) scanf("%lf%lf%lf",&a,&b,&c);
#define sr4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d);
#define f(i,a,n) for(int i=a;i<=n;i++)
#define ff(i) for(int i=1;i<=n;i++)
#define sc(x) cout<<#x<<" : "<<x<<endl;
#define hh cout<<endl;
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
#define dd double
#define inf 0x3f3f3f3f
#define ll __int128
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return w==1?x:-x;
}
inline void write(ll x)
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
const int N=1e6+5;
int d[N],vis[N];
int ver[N],edge[N],nnext[N],head[N];
int tot=1;
int t,r;
int n,m;
int k;
int p[N],a[N];
int dist[22][22];
dd dp[1<<18][22];
void add(int x,int y,int z)
{
ver[++tot]=y,edge[tot]=z;
nnext[tot]=head[x],head[x]=tot;
}
void addd(int x,int y,int z)
{
add(x,y,z),add(y,x,z);
}
priority_queue<pii,vector<pii>,greater<pii>>hp;
void dijkstra(int root)
{
mst(d,inf);
mst(vis,0);
d[root]=0;
hp.push(mk(d[root],root));
while(!hp.empty())
{
auto top=hp.top();
hp.pop();
if(vis[top.second])continue;
vis[top.second]=1;
for(int i=head[top.second];i;i=nnext[i])
{
int y=ver[i],e=edge[i];
if(d[top.second]+e>d[y])continue;
d[y]=d[top.second]+e;
hp.push(mk(d[y],y));
}
}
}
vector<pii> e[N];
void dijkstra2(int root)
{
mst(d,inf);
mst(vis,0);
d[root]=0;
hp.push(mk(d[root],root));
while(!hp.empty())
{
auto top=hp.top();
hp.pop();
if(vis[top.second])continue;
vis[top.second]=1;
for(auto v : e[top.second])
{
if(d[top.second]+v.second>=d[v.first])continue;
d[v.first]=d[top.second]+v.second;
hp.push({d[v.first],v.first});
}
}
}
inline void solve()
{
sr4(t,r,n,m);
f(i,1,m)
{
int x,y,z;
sr3(x,y,z);
addd(x,y,z);
e[x].push_back({y,z});
e[y].push_back({x,z});
}
sr(k);
f(i,0,k-1)sr2(a[i],p[i]);
a[k]=1,a[k+1]=n;
f(i,0,k+1)
{
dijkstra(a[i]);
f(j,0,k+1)dist[i][j]=d[a[j]];
}
if(dist[k][k+1]==inf)
{
puts("-1");
return;
}
for(int z=(1<<k)-1;z>=0;z--)
{
f(i,0,k-1)
if(z&(1<<i))
{
dd pb=0.01*p[i];
dd pg=1.0*dist[i][k+1]/r;
dd bb=1.0*dist[i][k+1]/t;
f(j,0,k-1)
{
if(!(z& (1<<j)))
bb=min(bb,1.0*dist[i][j]/t+dp[z|(1<<j)][j]);
}
dp[z][i]=pb*bb+(1-pb)*pg;
}
}
dd ans=1.0*dist[k][k+1]/t;
f(i,0,k-1)
{
ans=min(ans,1.0*dist[k][i]/t+dp[1<<i][i]);
}
printf("%.6lf",ans);
}
signed main()
{
int T=1;
for(int i=1;i<=T;i++)
{
solve();
}
return 0;
}
I - Power and Zero
题目链接I - Power and Zero
#include<bits/stdc++.h>
#define mst(s,x) memset(s,x,sizeof(s));
#define sr(x) scanf("%d",&x);
#define sr2(a,b) scanf("%d%d",&a,&b);
#define sr3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define sr3d(a,b,c) scanf("%lf%lf%lf",&a,&b,&c);
#define sr4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d);
#define f(i,a,n) for(int i=a;i<=n;i++)
#define ff(i) for(int i=1;i<=n;i++)
#define sc(x) cout<<#x<<" : "<<x<<endl;
#define hh cout<<endl;
#define dd double
#define inf 0x3f3f3f3f
#define ll __int128
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return w==1?x:-x;
}
inline void write(ll x)
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
const int N=1e5+5;
int a[N];
int n;
int cw[N];
void dfs(int cnt,int length)
{
if(cnt<0)return;
if(cnt>length)return;
if(cw[cnt]<cw[cnt+1])
{
int cz=cw[cnt+1]-cw[cnt];
int xc=ceil((dd)cz/3);
cw[cnt]+=xc*2;
cw[cnt+1]-=xc;
dfs(cnt-1,length);
}
dfs(cnt+1,length);
}
inline void solve()
{
mst(cw,0);
sr(n);
ff(i)sr(a[i]);
ff(i)for(int j=0;j<=30;j++) if(a[i]&(1<<j))cw[j]++;
int length=0;
for(int i=0;i<=30;i++)if(cw[i]!=0)length=i;
dfs(0,length);
printf("%d\n",cw[0]);
}
signed main()
{
int T=1;
cin>>T;
for(int i=1;i<=T;i++)
{
solve();
}
return 0;
}
J - Local Minimum
题目链接J - Local Minimum
#include<bits/stdc++.h>
#define mst(s,x) memset(s,x,sizeof(s));
#define sr(x) scanf("%d",&x);
#define sr2(a,b) scanf("%d%d",&a,&b);
#define sr3(a,b,c) scanf("%d%d%d",&a,&b,&c);
#define sr3d(a,b,c) scanf("%lf%lf%lf",&a,&b,&c);
#define sr4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d);
#define f(i,a,n) for(int i=a;i<=n;i++)
#define sc(x) cout<<#x<<" : "<<x<<endl;
#define hh cout<<endl;
#define dd double
#define inf 0x3f3f3f3f
#define ll __int128
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return w==1?x:-x;
}
inline void write(ll x)
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
const int N=1e3+5;
int n,m;
int mat[N][N];
int vis[N][N];
int hz[N];
int lz[N];
void solve()
{
sr2(n,m);
f(i,1,n)f(j,1,m)sr(mat[i][j]);
mst(hz,inf);
mst(lz,inf);
f(i,1,n)f(j,1,m)hz[i]=min(hz[i],mat[i][j]);
f(i,1,n)f(j,1,m)lz[j]=min(lz[j],mat[i][j]);
int ans=n*m;
f(i,1,n)f(j,1,m)if(mat[i][j]>hz[i]||mat[i][j]>lz[j])ans--;
cout<<ans<<endl;
}
signed main()
{
int T=1;
for(int i=1;i<=T;i++)
{
solve();
}
return 0;
}
|