今天大部分时间都花在了上一场沈阳站的L题上了,一个树上背包+容斥原理,看了好久才理解,就不硬敲上了,再想几天在写题解。然后今天自己写了场ICPC墨西哥站的
ICPC Gran Premio de Mexico 1ra Fecha
H. Hog Fencing
签到题,考察了基本不等式这个小知识点。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+5;
const int inf=1e18;
const int mod=1e9+7;
/*
int fac[40];
int qpow(int a,int b){
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
double n;
void solve()
{
cin>>n;
double g=(floor(n*n/16));
int k=(int)sqrt(g);
if(k*(k+1)<=g)
cout<<k*(k+1)<<endl;
else
cout<<k*k<<endl;
}
signed main()
{
ios;
//int T;cin>>T;
//while(T--)
solve();
return 0;
}
I. Isabel’s Divisions
签到题,stoi可将字符串转化为10进制数,真是个好工具。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+5;
const int inf=1e18;
const int mod=1e9+7;
/*
int fac[40];
int qpow(int a,int b){
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
int n;
string s;
void solve()
{
cin>>s;
int g=stoi(s);
n=s.length();s=" "+s;
int ans=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='0') continue;
if(g%(s[i]-'0')==0)
ans++;
}
cout<<ans<<endl;
}
signed main()
{
ios;
//int T;cin>>T;
//while(T--)
solve();
return 0;
}
J. Jeffrey’s ambition
第一个想法是用二分图去写,看了下时限0.3秒,但还是想用带时间戳的二分图试一下,不出意外,tle了,但是!!!问题出现在longlong上,关掉就可以过。
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e6+5;
const int inf=1e18;
const int mod=998244353;
/*
int fac[40];
int qpow(int a,int b){
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
int n,m,cnt,head[10005],link[10005],used[10005],ans,now;
struct node
{
int to,nxt;
}e[N];
void add(int u,int v)
{
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int dfs(int u)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(used[v]!=now)
{
used[v]=now;
if(link[v]==-1||dfs(link[v]))
{
link[v]=u;return 1;
}
}
}
return 0;
}
void hungary()
{
for(int i=0;i<=m;i++) link[i]=-1;
for(int i=1;i<=n;i++)
{
now++;
if(dfs(i)) ans++;
}
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int k;cin>>k;
for(int j=1;j<=k;j++)
{
int v;cin>>v;add(i,v);
}
}
hungary();
int g=0;
for(int i=1;i<=m;i++)
if(link[i]==-1) g++;
cout<<g<<endl;
}
signed main()
{
ios;
//int T;cin>>T;
//while(T--)
solve();
return 0;
}
最大流写法:核心在与建图文章来源:https://www.toymoban.com/news/detail-451925.html
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+5;
const int inf=1e18;
const int mod=998244353;
/*
int fac[40];
int qpow(int a,int b){
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
struct edge
{
int to,c,nxt;
}e[N*10];
int n,m,r[N],c[N],s,t,sum;
int head[N],idx=1;
int d[N],cur[N];
void add(int a,int b,int c)
{
e[++idx]={b,c,head[a]};
head[a]=idx;
}
bool bfs()
{
memset(d,0,sizeof d);
queue<int>q;
q.push(s);
d[s]=1;
while(q.size())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(d[v]==0&&e[i].c)
{
d[v]=d[u]+1;
q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
int dfs(int u,int mf)
{
if(u==t) return mf;
int sum=0;
for(int i=cur[u];i;i=e[i].nxt)
{
cur[u]=i;
int v=e[i].to;
if(d[v]==d[u]+1&&e[i].c)
{
int f=dfs(v,min(mf,e[i].c));
e[i].c-=f;
e[i^1].c+=f;
sum+=f;
mf-=f;
if(mf==0) break;
}
}
if(sum==0) d[u]=0;
return sum;
}
int dinic()
{
int flow=0;
while(bfs())
{
memcpy(cur,head,sizeof head);
flow+=dfs(s,inf);
}
return flow;
}
void solve()
{
cin>>n>>m;
s=0,t=n+m+1;
for(int i=1;i<=n;i++)
add(0,i,1),add(i,0,0);
for(int i=1;i<=m;i++)
add(i+n,t,1),add(t,i+n,0);
for(int i=1;i<=n;i++)
{
int k;cin>>k;
for(int j=1;j<=k;j++)
{
int v;cin>>v;
add(i,n+v,1),add(n+v,i,0);
}
}
int ans=dinic();
cout<<m-ans<<endl;
}
signed main()
{
//ios;
//int T;cin>>T;
//while(T--)
solve();
return 0;
}
K. Kilo Waste
一个完全背包,预处理出1~50000中的数字,判断每个数能否到达。
有一点读错了,低了假题,wa了一次。需要注意的是,浪费是指买多了,如果米买少了,不是浪费,此处理解错了。文章来源地址https://www.toymoban.com/news/detail-451925.html
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=7e5+5;
const int inf=1e18;
const int mod=998244353;
/*
int fac[40];
int qpow(int a,int b){
int res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int getinv(int x){return qpow(x,mod-2);}
int C(int a,int b)
{
return (fac[a]*getinv(fac[a-b])%mod)*getinv(fac[b])%mod;
}*/
int k,p,a[N],f[N];
void solve()
{
cin>>k>>p;
int mi=inf;
for(int i=1;i<=p;i++)
cin>>a[i],mi=min(mi,a[i]);
f[0]=1;
for(int i=1;i<=p;i++)
{
for(int j=a[i];j<=50000+mi;j++)
f[j]=max(f[j],f[j-a[i]]);
}
while(k--)
{
int x;cin>>x;
int g=0,s=0;
while(g<=mi&&f[x+g]==0) g++;
cout<<g<<endl;
}
}
signed main()
{
//ios;
//int T;cin>>T;
//while(T--)
solve();
return 0;
}
到了这里,关于2022 ICPC Gran Premio de Mexico 1ra Fecha(一)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!