B题
假设我们考虑能不能获得1，注意到b-c的奇偶性不会改变，然后特判一下只有一个大于0就行。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
//#define A puts("YES")
//#define B puts("NO")
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=2e5+5;
int a,b,c,x,y,z;
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
x=y=z=0;
scanf("%d %d %d",&a,&b,&c);
int t=(a>0)+(b>0)+(c>0);
if ((b-c)%2==0 && t>1) x=1;
if ((a-c)%2==0 && t>1) y=1;
if ((a-b)%2==0 && t>1) z=1;
printf("%d %d %d\n",x,y,z);
}
return 0;
}
C题显然直接dp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
//#define A puts("YES")
//#define B puts("NO")
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int inf=1<<30;
const int N=3e5+5;
int n,x,y,a[N],l[N],r[N],f[N];
char s[N];
void cmin(int &x,int y){
x=min(x,y);
}
void dfs(int x){
if (l[x]) {
dfs(l[x]);
cmin(f[x], f[l[x]]+(a[x]!=1));
}
if (r[x]) {
dfs(r[x]);
cmin(f[x], f[r[x]]+(a[x]!=2));
}
if (!l[x] && !r[x]) f[x]=0;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%d",&n);
scanf("%s",s+1);
fo(i,1,n) {
if (s[i]=='U') a[i]=0;
if (s[i]=='L') a[i]=1;
if (s[i]=='R') a[i]=2;
}
fo(i,1,n) {
l[i]=r[i]=0;
scanf("%d %d",&x,&y);
l[i]=x;
r[i]=y;
}
fo(i,1,n) f[i]=inf;
dfs(1);
printf("%d\n",f[1]);
}
return 0;
}
D题的套路感觉见过很多次了
设\(ans[d]\)表示d|\(f(a,b,c)\)的答案,那么我们减去所有2d，3d...kd的答案就是d的答案。
计算ans[d]直接从小到大考虑就行。
复杂度分析是经典的O(nlnn)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
//#define A puts("YES")
//#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=1e5+5;
ll a[N],n,s[N],b[N],tot,c[N],ans,d,x,t;
ll f[N],g[N];
ll c2(ll x){
return x*(x-1)/2;
}
ll c3(ll x){
return x*(x-1)*(x-2)/6;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
fo(i,1,N-1) f[i]=g[i]=c[i]=0;
ans=0;
scanf("%lld",&n);
fo(i,1,n) {
scanf("%lld",&x);
c[x]++;
}
fo(i,1,N-1) s[i]=s[i-1]+c[i];
// f[n] only calc the number
fo(i,1,1e5) {
fo(j,1,1e5/i) {
x=i*j;
t=c[x];
if (t>=2) f[i]+=c2(t)*(n-s[x]);
if (t>=3) f[i]+=c3(t);
f[i]+=g[i]*t*(n-s[x]);
if (t>=2) f[i]+=g[i]*c2(t);
g[i]+=t;
}
}
ans=0;
fd(i,1e5,1) {
fo(j,2,1e5/i) {
f[i]-=f[i*j];
}
ans+=f[i]*i;
}
printf("%lld\n",ans);
}
return 0;
}
E题显然就是tarjan缩点之后dp
板子题
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
//#define A puts("YES")
//#define B puts("NO")
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll inf=1ll<<60;
const int N=3e5+5;
ll a[N];
int n,m,x,y;
ll dfn[N],low[N],st[N],cnt,top,num,w[N],c[N];
int to[N*2],nex[N*2],head[N],tot,d[N],sz[N];
ll f[N],g[N];
bool ins[N];
vector<int> v[N];
queue<int> q;
void add(int x,int y){
to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x){
dfn[x]=low[x]=++num;
st[++top]=x; ins[x]=1;
for (int i=head[x];i;i=nex[i]) {
int v=to[i];
if (!dfn[v]) {
dfs(v);
low[x]=min(low[x], low[v]);
}
else if (ins[v]) low[x]=min(low[x],dfn[v]);
}
if (dfn[x]==low[x]) {
++cnt; int y;
w[cnt]=0;
v[cnt].clear();
d[cnt]=0;
sz[cnt]=0;
f[cnt]=inf;
g[cnt]=0;
do{
y=st[top--];
w[cnt]+=a[y];
ins[y]=0;
c[y]=cnt;
sz[cnt]++;
}while (x!=y);
}
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("ans.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%d %d",&n,&m);
fo(i,1,n) scanf("%lld",&a[i]);
tot=0;
fo(i,1,n) head[i]=0;
fo(i,1,m) {
scanf("%d %d",&x,&y);
add(x,y);
}
cnt=top=num=0;
fo(i,1,n) dfn[i]=0;
fo(i,1,n) {
if (!dfn[i]) dfs(i);
}
fo(i,1,cnt) v[i].clear(),d[i]=0;
fo(x,1,n) {
for (int i=head[x];i;i=nex[i]){
int y=to[i];
if (c[x]==c[y]) continue;
v[c[y]].emplace_back(c[x]);
d[c[x]]++;
}
}
while (!q.empty()) q.pop();
fo(i,1,cnt) if (!d[i]) q.push(i),f[i]=w[i],g[i]=sz[i];
while (!q.empty()) {
x=q.front(); q.pop();
for(int y:v[x]) {
if (g[x]+sz[y]>g[y]) {
g[y]=g[x]+sz[y];
f[y]=f[x]+w[y];
}
else if (g[x]+sz[y]==g[y]) {
f[y]=min(f[y], f[x]+w[y]);
}
d[y]--;
if (!d[y]) q.push(y);
}
}
ll ans=inf,l=0;
fo(i,1,cnt) {
if (g[i]>l) {
l=g[i];
ans=f[i];
}
else if (g[i]==l) ans=min(ans, f[i]);
}
printf("%lld %lld\n",l,ans);
}
return 0;
}