T1 karma
题解
首先从贪心的思路出发
把所有零多的字符串放在前面，但如下一组数据便可以卡掉
2
0
1100
接着我们可以来思考对于贪心的更改
多举几组不同的可以卡掉的样例后可以发现如下规律
先将所有字符串按 \(0\) 的数量排一遍序
对于每一个字符串的 \(0\) 和 \(1\) 的数量我们分别记为 \(a_i\) 和 \(b_i\)
那么如果 \(a_i \times b_{i+1} > a_{i+1} \times b_i\)
那么便交换 \(i\) 和 \(i+1\)
感性理解一下，还是挺正确的你别说就是能过
#include<bits/stdc++.h>
#define N 200010
using namespace std;
struct node{
int a,b,zero;
}a[N];
int n,tot;
long long ans;
bool cmp(node x,node y){
return x.zero==y.zero?x.b<y.b:x.zero>y.zero;
}
bool cmp2(node x,node y){
return x.zero*y.b>y.zero*x.b;
}
int main(){
freopen("karma.in","r",stdin);
freopen("karma.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i<=n;i++){
string s;int tmp = 0;
cin>>s;
for(int j = 0;j<s.size();j++){
if(s[j]=='1') a[i].b++;
else a[i].a+=a[i].b,a[i].zero++;
}
}
sort(a+1,a+n+1,cmp);
sort(a+1,a+n+1,cmp2);
for(int i = 1;i<=n;i++){
ans+=a[i].a+a[i].zero*tot;
tot+=a[i].b;
}
cout<<ans;
return 0;
}
以下为题解做法，其实差距不大
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+7;
const int M=1e7+7;
char s[M];
pair<int,int>A[N];
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n;scanf("%d",&n);
ll ans=0;
for(int i=0;i<n;++i){
scanf("%s",s);
int m=strlen(s);
int cnt=0;
for(int j=0;j<m;++j){
if(s[j]=='0'){
ans+=cnt;
}
else {
cnt++;
}
}
A[i]={m-cnt,cnt};
}
sort(A,A+n,[](const pair<int,int> &A, const pair<int,int> &B){return (ll)A.first*B.second>(ll)A.second*B.first;});
int sum=0;
for(int i=0;i<n;++i){
ans+=(ll)A[i].first*sum;
sum+=A[i].second;
}
printf("%lld\n",ans);
return 0;
}
T2 desire
题解
正解也比较好想，但是我比赛时想的太麻烦而没有写出来
我宣布个事啊，wssb 假设有 \(x\) 条路径经过这个点，有 \(y\) 条路径以该点为最高点
那么方案数就是 \(\binom x k − \binom {x-y} k\)，然后把方案数求和即可
证明一下
对于一条路径，我们只在它的最高点进行统计，统计这条路径已经确定要被选的方案数
对于不以当前点为最高点的路径，他们一定会在当前节点上方有一段是重合的，直到有一条路径到了它的最高点
所以这些路径间相互组合的便会算重，必须减去
#include<bits/stdc++.h>
#define mod ((int)1e9+7)
#define N 2000010
using namespace std;
struct edge{
int v,ne;
}e[N<<1];
int n,m,k,cnt,fac[N],inv[N],fa[N][25],dep[N],h[N],ans,f[N],g[N];
int ksm(int x,int y){
int res = 1;
while(y){
if(y&1) res = 1ll*res*x%mod;
x = 1ll*x*x%mod;
y>>=1;
}
return res;
}
void add(int u,int v){
e[++cnt].v = v;
e[cnt].ne = h[u];
h[u] = cnt;
}
int C(int x,int y){
if(x<y) return 0;
return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void dfs(int x,int father){
dep[x] = dep[father]+1;
fa[x][0] = father;
for(int i = 1;(1<<i)<=dep[x];i++)
fa[x][i] = fa[fa[x][i-1]][i-1];
for(int i = h[x];i;i = e[i].ne){
int v = e[i].v;
if(v==father) continue;
fa[v][0] = x;
dfs(v,x);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
int z = dep[x]-dep[y];
for(int i = 0;(1<<i)<=z;i++)
if(z&(1<<i)) x = fa[x][i];
if(x==y) return x;
for(int i = 22;i>=0;i--){
if(fa[x][i]!=fa[y][i])
x = fa[x][i],y = fa[y][i];
}
return fa[x][0];
}
void dfs2(int x){
for(int i = h[x];i;i = e[i].ne){
int v = e[i].v;
if(v==fa[x][0]) continue;
dfs2(v);
g[x]+=g[v];
}
ans = (1ll*ans+C(f[x]+g[x],k)-C(g[x],k)+mod)%mod;
}
int main(){
freopen("desire.in","r",stdin);
freopen("desire.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
fac[0] = 1;
for(int i = 1;i<=m;i++) fac[i] = 1ll*fac[i-1]*i%mod;
inv[m] = ksm(fac[m],mod-2);
for(int i = m-1;i>=0;i--) inv[i] = 1ll*inv[i+1]*(i+1)%mod;
for(int i = 1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);add(v,u);
}
dfs(1,0);
for(int i = 1;i<=m;i++){
int u,v;
cin>>u>>v;
int l = lca(u,v);
f[l]++;g[u]++;g[v]++;
g[l]-=2;
}
dfs2(1);
cout<<ans;
return 0;
}
T3 courage
题解
树形 \(dp\) 题，有点难懂
对于第一个询问
\(f[i][j]\) 表示 \(i\) 的子树，还有 \(j\) 个节点未匹配的方案数，\(f'[i][j]\) 为一个临时数组
枚举子树 \(v\) 合并\(f′[i][j] = f[i][j-k] \times f[v][k]\)
然后枚举 \(i\) 点的选择 \(f[i][j] = f′[i][j−1]+f′[i][j+1]\times(j+1)\)。
设 \(f[i][j]\) 表示钦定了未匹配点的匹配顺序时的方案数，\(g[i][J]\) 表示所有方案的交点之和。
这样 \(f[i][j]\) 先枚举子树 \(v\) 合并 $f'[i][s] = \sum\limits_{k} f'[i][k] \times f[v][s-k]\times \binom s k $
组合数是合并匹配顺序序列的方案，然后选择 \(i\) 的情况，
\(f[i][j] = f'[i][j-1]\times j+f'[i-1][j+1]\)
\(g'[i][s] = \sum\limits_s (f'[i][k]\times g[v][s-k]+g'[i][k] \times f[v][s-k])\times \binom s k\)
\(g[i][j] = g'[i][j+1]+g[i][j-1]\times j+f'[i][j-1]\times \frac{j\times(j-1)}{2}\)
#include<bits/stdc++.h>
#define N 2010
#define mod 998244353
#define ll long long
using namespace std;
int n,inv2 = (mod+1)/2,siz[N],f[N][N],g[N][N],tmpf[N],tmpg[N];
vector<int>e[N];
void dfs(int u,int fa){
f[u][0] = 1;
for(int v : e[u]){
if(v==fa) continue;
dfs(v,u);
for(int i = 0;i<=siz[u]+siz[v];i++)
tmpf[i] = tmpg[i] = 0;
for(int i = 0;i<=siz[u];i++){
for(int j = 0;j<=siz[v];j++){
tmpf[i+j] = (tmpf[i+j]+(ll)f[u][i]*f[v][j])%mod;
tmpg[i+j] = (tmpg[i+j]+(ll)g[u][i]*f[v][j]+(ll)f[u][i]*g[v][j])%mod;
}
}
siz[u]+=siz[v];
for(int i = 0;i<=siz[u]+siz[v];i++)
f[u][i] = tmpf[i],g[u][i] = tmpg[i];
}
siz[u]++;
for(int i = 0;i<=siz[u];i++)
tmpf[i] = tmpg[i] = 0;
for(int i = 0;i<siz[u];i++){
if(i){
tmpf[i-1] = (tmpf[i-1]+(ll)f[u][i]*i)%mod;
tmpg[i-1] = (tmpg[i-1]+(ll)g[u][i]*i)%mod;
}
tmpf[i+1] = (tmpf[i+1]+f[u][i])%mod;
tmpg[i+1] = (tmpg[i+1]+g[u][i]+(ll)i*f[u][i])%mod;
}
for(int i = 0;i<=siz[u];i++)
f[u][i] = tmpf[i],g[u][i] = tmpg[i];
}
int main(){
freopen("courage.in","r",stdin);
freopen("courage.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i = 1;i<n;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
cout<<(f[1][0]+mod)%mod<<" "<<((ll)g[1][0]*inv2%mod+mod)%mod;
return 0;
}
T4 innocent
大意：给定一张 \(n\) 个节点 \(m\) 条边的有向带权图，对每个节点，若不存在奇权圈（可经过重复顶点、重复边，若经过重复边，边权计多次），输出 \(a-w-r-y\)，否则，输出最小奇权圈的权值（负无穷输出 \(Twinkle\)）。
题解
首先用 \(tarjan\) 算法将图分为若干个强连通子图，针对每个强连通子图分别进行计算。
因为题目只管环的权值，所以我们不需要处理强连通子图之间的关系
给定一个强连通子图，构造新的图，每个点 \(x\) 拆分为两个节点 \(Odd_x\) 和 \(Even_x\)
对一条权值为 \(w\) 的边 \((x,y)\)，若 \(w\) 是奇数，添加权值为\(w\) 的 \((Odd_x,Even_y)\) 和 \((Even_x,Odd_y)\) 两条边
否则添加权值为 \(w\) 的 \((Odd_x,Odd_y)\) 和 \((Even_x,Even_y)\)两条边
在新图上用 \(Bellman ford\) 之类的算法判断是否存在负权圈我用的某个已死的算法
如果存在负权圈，则对每个节点 \(x\) 判断 \(Odd_x\) 能否到达 \(Even_x\)，若能，输出 \(Twinkle\)，否则输出 \(a-w-r-y\)
如果不存在负权圈，使用 \(Johnson\) 算法跑全源最短路
对每个节点 \(x\)，若 \(Odd_x\) 能到达 \(Even_x\)，输出路径长度，否则输出 \(a-w-r-y\)。
#include<bits/stdc++.h>
#define inf (0x3f3f3f3f3f3f3f3fll)
#define ll long long
#define N 1010
using namespace std;
struct edge{
int v,ne;
ll w;
};
struct johnson{
int h[N<<1],t[N<<1],vis[N<<1],cnt,siz;
ll w[N<<1],dis[N<<1];
vector<int>nd;
edge e[N*20];
struct node{
ll dis,id;
bool operator <(const node& a)const{
return dis>a.dis;
}
};
void add(int u,int v,ll w){
e[++cnt] = {v,h[u],w};
h[u] = cnt;
}
bool spfa(int s){
queue<int>q;
memset(w,0x3f,sizeof(w));
memset(t,0,sizeof(t));
memset(vis,0,sizeof(vis));
w[s] = 0;q.push(s);vis[s] = 1;
while(q.size()){
int u = q.front();q.pop();
vis[u] = 0;
for(int i = h[u];i;i = e[i].ne){
int v = e[i].v;
if(w[u]+e[i].w<w[v]){
w[v] = max(-inf,w[u]+e[i].w);
t[v] = t[u]+1;
if(t[v]>=2*siz) return false;
if(vis[v]) continue;
q.push(v);
vis[v] = 1;
}
}
}
return true;
}
void dij(int s){
priority_queue<node>q;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s] = 0;q.push((node){0,s});
while(q.size()){
int u = q.top().id;q.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = h[u];i;i = e[i].ne){
int v = e[i].v;
if(dis[v]>dis[u]+e[i].w+w[u]-w[v]){
dis[v] = dis[u]+e[i].w+w[u]-w[v];
if(!vis[v]) q.push((node){dis[v],v});
}
}
}
}
bool check(int x,int ed){
if(x==ed) return true;
bool ans = false;
for(int i = h[x];i;i = e[i].ne){
int v = e[i].v;
if(!vis[v]){
vis[v] = true;
ans = ans||check(v,ed);
}
}
return ans;
}
}gg;
vector<johnson>g;
int n,m,scc,col[N],dfn[N],low[N],dfncnt;
ll ans[N];
bool vis[N];
stack<int>stk;
int odd(int x){
return x<<1|1;
}
int even(int x){
return x<<1;
}
void tarjan(int x){
dfn[x] = low[x] = ++dfncnt;
stk.push(x);vis[x] = true;
for(int i = gg.h[x];i;i = gg.e[i].ne){
int v = gg.e[i].v;
if(!dfn[v]){
tarjan(v);
low[x] = min(low[x],low[v]);
}else if(vis[v]) low[x] = min(dfn[v],low[x]);
}
if(dfn[x]==low[x]){
col[x] = ++scc;
while(stk.top()!=x){
col[stk.top()] = scc;
vis[stk.top()] = false;
stk.pop();
}
vis[stk.top()] = false;
stk.pop();
}
}
signed main(){
freopen("innocent.in","r",stdin);
freopen("innocent.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i = 1;i<=m;i++){
int u,v;ll w;
cin>>u>>v>>w;
u++;v++;
gg.add(u,v,w);
}
for(int i = 1;i<=n;i++)
if(!dfn[i]) tarjan(i);
g.resize(scc+2);
for(int i = 1;i<=n;i++){
g[col[i]].siz++;
g[col[i]].nd.push_back(i);
for(int j = gg.h[i];j;j = gg.e[j].ne){
int v = gg.e[j].v;ll w = gg.e[j].w;
if(col[v]!=col[i]) continue;
if(w&1){
g[col[i]].add(odd(i),even(v),w);
g[col[i]].add(even(i),odd(v),w);
}else{
g[col[i]].add(odd(i),odd(v),w);
g[col[i]].add(even(i),even(v),w);
}
}
}
for(int i = 1;i<=scc;i++){
if(!g[i].spfa(even(g[i].nd[0]))){
for(int j : g[i].nd){
memset(g[i].vis,0,sizeof(g[i].vis));
if(g[i].check(even(j),odd(j))) ans[j] = -inf;
else ans[j] = inf;
}
continue;
}
for(int u : g[i].nd){
memset(g[i].vis,0,sizeof(g[i].vis));
if(!g[i].check(even(u),odd(u))){
ans[u] = inf;
continue;
}
g[i].dij(even(u));
ans[u] = g[i].dis[odd(u)]+g[i].w[odd(u)]-g[i].w[even(u)];
}
}
for(int i = 1;i<=n;i++){
if(ans[i]==-inf) cout<<"Twinkle\n";
else if(ans[i]==inf) cout<<"a-w-r-y\n";
else cout<<ans[i]<<"\n";
}
return 0;
}
附上一篇比较短的代码，某位大佬貌似是用 \(SPFA\) 卡过去的
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define int long long
#define LL long long
#define pi pair<int,int >
#define mpr make_pair
using namespace std;
const int N = 1e3+5,M = 1e4+5,mod = 998244353,inf = 1e15;
inline int read() {
int s=0,w=1; char ch=getchar();
while( ch>'9'|| ch<'0') {if(ch=='-') w=-1; ch=getchar();}
while(ch<='9'&&ch>='0') {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*w;
}
inline int Mod(int x) {return x>=mod?x-mod:x;}
inline void addmod(int &x,int y) {x=Mod(x+y);}
inline void chkmax(auto &x,auto y) {x=(x>y?x:y);}
inline void chkmin(auto &x,auto y) {x=(x<y?x:y);}
namespace starrylasky {
int n,m,tot,cnt,tp,tim,cc,p[N],f[N],be[N],s[N],dfn[N],low[N],head[N],d[N][2],c[N][2],ans[N];
bool vis[N],past[N][2];
struct Edge {
int v,nxt,w;
}e[M];
inline void add(int u,int v,int w) {
e[++tot]={v,head[u],w}; head[u]=tot;
}
inline int spfa(int t,int type) {
fep(i,1,cc) fep(j,0,1) d[p[i]][j]=inf,c[p[i]][j]=past[p[i]][j]=0;
queue<pi > q; q.push(mpr(t,0)); d[t][0]=0;
while(!q.empty()) {
int u=q.front().first,p=q.front().second; q.pop(); past[u][p]=0;
For(i,u) if(be[u]==be[e[i].v]) {
int ret=d[u][p]+e[i].w,id=(ret%2+2)&1;
if(d[e[i].v][id]>ret&&(type||c[e[i].v][id]<=n)) {
if(c[e[i].v][id]>n) return -inf;
if(!past[e[i].v][id]) q.push(mpr(e[i].v,id)),past[e[i].v][id]=1;
++c[e[i].v][id]; d[e[i].v][id]=ret;
}
}
}
return d[t][1];
}
inline void tarjan(int u) {
dfn[u]=low[u]=++tim; s[++tp]=u; vis[u]=1;
For(i,u) {
if(!dfn[e[i].v]) tarjan(e[i].v),chkmin(low[u],low[e[i].v]);
else if(vis[e[i].v]) chkmin(low[u],dfn[e[i].v]);
}
if(dfn[u]==low[u]) {
++cnt; cc=0;
while(s[tp+1]!=u) {
vis[s[tp]]=0; be[s[tp]]=cnt;
p[++cc]=s[tp--];
}
f[cnt]=spfa(p[1],1)==-inf;
fep(i,1,cc) {
ans[p[i]]=spfa(p[i],0);
if(ans[p[i]]==inf) {
fep(j,i,cc) ans[p[j]]=inf;
break;
}
else if(f[cnt]) {
break;
}
}
}
}
inline void Main() {
n=read(),m=read();
fep(i,1,m) {
int u=read()+1,v=read()+1,w=read();
add(u,v,w);
}
fep(i,1,n) if(!dfn[i]) tarjan(i);
fep(i,1,n) {
if(ans[i]==inf) puts("a-w-r-y");
else if(f[be[i]]) puts("Twinkle");
else printf("%lld\n",ans[i]);
}
}
}
signed main() {
freopen("innocent.in","r",stdin);
freopen("innocent.out","w",stdout);
int _T=1;
while(_T--) starrylasky::Main();
return 0;
}