如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
Problem G. Cyclic
递推。
#include<stdio.h>
#define N 100009
#define M 998244353
#define mul(a,b,c) ((a)*(b)%(c))
typedef long long ll;
ll t,n,f[N]= {0,1,0,1,1};
int main()
{
for(ll i=5; i<N; ++i)
f[i]=(mul(i-3,f[i-1],M)+mul(2*i-4,f[i-2],M)+mul(i-2,f[i-3],M))%M;
for(scanf("%lld",&t); t--; printf("%lld\n",f[n]))
scanf("%lld",&n);
}
Problem H. Pow
交了一个高精度。
#include<bits/stdc++.h>
using namespace std;
struct Wint:vector<int>
{
static const int width=9,base=1e9;
Wint(unsigned long long n=0)
{
for(; n; n/=base)push_back(n%base);
}
explicit Wint(const string &s)
{
for(int len=int(s.size()-1)/width+1,b,e,i=0; i!=len; ++i)
for(e=s.size()-i*width,b=max(0,e-width),push_back(0); b!=e; ++b)
back()=back()*10+s[b]-'0';
trim(0);
}
Wint& trim(bool up=1)
{
for(int i=1; up&&i<size(); ++i)
{
if(at(i-1)<0)--at(i),at(i-1)+=base;
if(at(i-1)>=base)at(i)+=at(i-1)/base,at(i-1)%=base;
}
while(!empty()&&back()<=0)pop_back();
for(; up&&!empty()&&back()>=base; at(size()-2)%=base)
push_back(back()/base);
return *this;
}
};
Wint& operator*=(Wint &a,const Wint &b)
{
Wint c;
c.assign(a.size()+b.size()+2,0);
for(int j=0,k,l; j<b.size(); ++j)
if(b[j])
for(int i=0; i<a.size(); ++i)
{
unsigned long long n=a[i];
for(n*=b[j],k=i+j; n; n/=c.base)c[k++]+=n%c.base;
for(l=i+j; c[l]>=c.base||l<k; c[l++]%=c.base)c[l+1]+=c[l]/c.base;
}
return swap(a,c),a.trim(0);
}
ostream& operator<<(ostream &os,const Wint &n)
{
if(n.empty())return os.put('0');
os<<n.back();
char ch=os.fill('0');
for(int i=n.size()-2; ~i; --i)
os.width(n.width),os<<n[i];
return os.fill(ch),os;
}
typedef Wint ll;
ll pow(ll a,int b)
{
ll r=1;
for(; b; b>>=1,a*=a)
if(b&1)r*=a;
return r;
}
int main()
{
int t,n;
for(cin>>t; t--; cout<<pow(ll(2),n)<<'\n')
cin>>n;
}
可以直接修改 cout 的浮点输出方式为指数形式输出。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n;
for(cin>>t; t--; cout<<fixed<<setprecision(0)<<pow(2,n)<<'\n')
cin>>n;
}
Problem I. Count
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct EulerSieve
{
vector<int> p,m,phi;
vector<ll> sum;
EulerSieve(int N):m(N,0),phi(N,0),sum(N,0)
{
phi[1]=1;
for(long long i=2,k; i<N; ++i)
{
if(!m[i])p.push_back(m[i]=i),phi[i]=i-1;
sum[i]=sum[i-1]+(i%2?phi[i]/2:phi[i]);
for(int j=0; j<p.size()&&(k=i*p[j])<N; ++j)
{
phi[k]=phi[i]*p[j];
if((m[k]=p[j])==m[i])break;
phi[k]-=phi[i];
}
}
}
} e(2e7+7);
int main()
{
ll t,n;
for(scanf("%lld",&t); t--; printf("%lld\n",e.sum[n]))scanf("%lld",&n);
}
Problem J. CSGO
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100000+10;
int t,n,m,k,v;
long long f[70],g[70];
int x[10];
long long ans;
int main()
{
scanf("%d",&t);
while (t--)
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
ans=0;
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++)
{
scanf("%d",&v);
for (int i=1;i<=k;i++) scanf("%d",&x[i]);
for (int j=0;j<(1<<(k+1));j++)
{
long long sum=v;
for (int l=1;l<=k;l++)
if ((1<<l)&j) sum+=x[l];
else sum-=x[l];
f[j]=max(f[j],sum);
}
}
for (int i=1;i<=m;i++)
{
scanf("%d",&v);
for (int i=1;i<=k;i++) scanf("%d",&x[i]);
for (int j=0;j<(1<<(k+1));j++)
{
long long sum=v;
for (int l=1;l<=k;l++)
if ((1<<l)&j) sum+=x[l];
else sum-=x[l];
ans=max(ans,sum+f[(1<<(k+1))-1-j]);
}
}
printf("%lld\n",ans);
}
return 0;
}
Problem L.Videos
最大费用流。
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF=1e9,NPOS=-1;
struct Graph
{
struct Vertex
{
vector<int> a;
};
struct Edge
{
int from,to;
ll dist,cap;
};
vector<Vertex> v;
vector<Edge> e;
Graph(int n):v(n) {}
void add(const Edge &ed)
{
v[ed.from].a.push_back(e.size());
e.push_back(ed);
}
};
struct EdmondKarp:Graph
{
ll flow,cost;
vector<ll> f;
EdmondKarp(int n):Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.from,ed.to),ed.cap=0,ed.dist*=-1;
Graph::add(ed);
}
void ask(int s,int t)
{
vector<int> p(v.size(),NPOS);
for(f.assign(e.size(),flow=cost=0);;)
{
vector<ll> d(v.size(),INF);
vector<int> flag(v.size(),d[s]=0);
for(deque<int> q(flag[s]=1,s); !q.empty(); q.pop_front())
for(int u=q.front(),i=flag[u]=0,k,to; i<v[u].a.size(); ++i)
if(k=v[u].a[i],to=e[k].to,
e[k].cap>f[k]&&d[to]>d[u]+e[k].dist)
{
d[to]=d[u]+e[k].dist,p[to]=k;
if(!flag[to])q.push_back(to),flag[to]=1;
}
if(d[t]==INF)return;
ll _f=INF;
for(int u=t; u!=s; u=e[p[u]].from)
_f=min(_f,e[p[u]].cap-f[p[u]]);
for(int u=t; u!=s; u=e[p[u]].from)
cost+=_f*e[p[u]].dist,f[p[u]]+=_f,f[p[u]^1]-=_f;
flow+=_f;
}
}
};
int t,n,m,k,w,S[255],T[255],W[255],P[255];
int main()
{
for(scanf("%d",&t); t--;)
{
scanf("%d%d%d%d",&n,&m,&k,&w);
EdmondKarp g(m*2+3);
for(int i=1; i<=m; ++i)
scanf("%d%d%d%d",&S[i],&T[i],&W[i],&P[i]);
for(int i=1; i<=m; ++i)
{
for(int j=1; j<=m; ++j)
if(S[j]>=T[i])
g.add({2*i+1,2*j,P[i]==P[j]?w:0,1});
g.add({1,2*i,0,1});
g.add({2*i,2*i+1,-W[i],1});
g.add({2*i+1,2*m+2,0,1});
}
g.add({0,1,0,k});
g.ask(0,2*m+2);
printf("%d\n",-g.cost);
}
}