头像

真-王善珑


访客:2887

离线:2小时前


新鲜事 原文

真-王善珑
14小时前
AcWing官方壁纸hh(bushi
图片


新鲜事 原文

真-王善珑
15小时前
突然发现了Ac Chat的小变化 发消息变快了欸(o(* ̄▽ ̄*)ブ


活动打卡代码 AcWing 2280. 最优标号

#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 510, M = (3000 + N * 2) * 2, INF = 1e8;

int n, m, k, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int p[N];
PII edges[3010];

void add(int a, int b, int c1, int c2)
{
    e[idx] = b, f[idx] = c1, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = c2, ne[idx] = h[b], h[b] = idx ++ ;
}

void build(int k)
{
    memset(h, -1, sizeof h);
    idx = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].x, b = edges[i].y;
        add(a, b, 1, 1);
    }
    for (int i = 1; i <= n; i ++ )
        if (p[i] >= 0)
        {
            if (p[i] >> k & 1) add(i, T, INF, 0);
            else add(S, i, INF, 0);
        }
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

LL dinic(int k)
{
    build(k);
    int r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

int main()
{
    scanf("%d%d", &n, &m);
    S = 0, T = n + 1;
    for (int i = 0; i < m; i ++ ) scanf("%d%d", &edges[i].x, &edges[i].y);
    scanf("%d", &k);
    memset(p, -1, sizeof p);
    while (k -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        p[a] = b;
    }

    LL res = 0;
    for (int i = 0; i <= 30; i ++ ) res += dinic(i) << i;
    printf("%lld\n", res);

    return 0;
}


活动打卡代码 AcWing 2279. 网络战争

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 810, INF = 1e8;
const double eps = 1e-8;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
double f[M];
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx ++ ;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i] > 0)
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T) return true;
                q[ ++ tt] = ver;
            }
        }
    }
    return false;
}

double find(int u, double limit)
{
    if (u == T) return limit;
    double flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i] > 0)
        {
            double t = find(ver, min(f[i], limit - flow));
            if (t < eps) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

double dinic(double mid)
{
    double res = 0;
    for (int i = 0; i < idx; i += 2)
        if (w[i] <= mid)
        {
            res += w[i] - mid;
            f[i] = f[i ^ 1] = 0;
        }
        else f[i] = f[i ^ 1] = w[i] - mid;

    double r = 0, flow;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r + res;
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    double l = 0, r = 1e7;
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (dinic(mid) < 0) r = mid;
        else l = mid;
    }

    printf("%.2lf\n", r);
    return 0;
}



每道题目链接:
P1001 A+B Problem
P1000 超级玛丽游戏
P5703 【深基2.例5】苹果采购
P5704 【深基2.例6】字母转换
P5705 【深基2.例7】数字反转
P5706 【深基2.例8】再分肥宅水
P1425 小鱼的游泳时间
2433 【深基1-2】小学数学 N 合一
P5708 【深基2.习2】三角形面积
P1421 小玉买文具
P5709 【深基2.习6】Apples Prologue
P2181 对角线

P1001 A+B Problem

比较简单的题,直接上代码:

#include <iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a+b;
    return 0;
}

P1000 超级玛丽游戏

比较毒瘤,手动打图,代码:

#include<iostream>
using namespace std;
int main()
{
    cout<<R"(                ********
               ************
               ####....#.
             #..###.....##....
             ###.......######              ###            ###
                ...........               #...#          #...#
               ##*#######                 #.#.#          #.#.#
            ####*******######             #.#.#          #.#.#
           ...#***.****.*###....          #...#          #...#
           ....**********##.....           ###            ###
           ....****    *****....
             ####        ####
           ######        ######
##############################################################
#...#......#.##...#......#.##...#......#.##------------------#
###########################################------------------#
#..#....#....##..#....#....##..#....#....#####################
##########################################    #----------#
#.....#......##.....#......##.....#......#    #----------#
##########################################    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#
##########################################    ############ )";  //你一定没见过的cout,多行输出真的爽
}

P5703 【深基2.例5】苹果采购

hh这题说了这么多其实就是a*b
那就好办喽:

#include <iostream>
using namespac std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a*b;
    return 0;
}

P5704 【深基2.例6】字母转换

这道题主要考察的就是大写字母比小写字母的ASCII码小32

#include <iostream>
using namespace std;
int main()
{
    char a;
    cin>>a;
    cout<<(char)(a-32);
}

P5705 【深基2.例7】数字反转

这题的正解比较好想,因为一共就是xxx.x的格式,所以用4个char读入再反过来输出hh

#include <iostream>
using namespace std;
int main()
{
    char a,b,c,d;
    scanf("%c%c%c.%c",&a,&b,&c,&d);
    cout<<d<<"."<<c<<b<<a;
    return 0;
}

这里再搞一个字符串做法

#include <iostream>
using namespace std;
int main()
{
    string a;
    cin>>a;
    for(int i = a.size() - 1;i >= 0;i --)
        cout<<a[i];
    return 0;
}

P5706 【深基2.例8】再分肥宅水

第一个输出是a / b保留三位小数
第二个是b * 2
代码如下:

#include <iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    printf("%.3f\n",(double)a/b);
    printf("%d",b*2);
    return 0;
}

P1425 小鱼的游泳时间

P2433 【深基1-2】小学数学 N 合一

P5708 【深基2.习2】三角形面积

P1421 小玉买文具

P5709 【深基2.习6】Apples Prologue

P2181 对角线



新鲜事 原文

近期文化课阶段,更新就放在B站上了(qwq文化课差的要炸掉了



#include<bits/stdc++.h>
using namespace std;

const int N=10010,M=100010*2+N*4;
int q[N],d[N],cur[N],h[N],ne[M],e[M],f[M],idx,n,m,S,T;
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    int tt=0,hh=0;
    q[0]=S,cur[S]=h[S],d[S]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}
int find(int u,int limit)
{
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];i!=-1&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t) d[ver]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int r=0,flow;
    while(bfs()) while(flow=find(S,0x3f3f3f3f)) r+=flow;
    return r;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m>>S>>T;
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout<<dinic()<<endl;
    return 0;
}


活动打卡代码 AcWing 2278. 企鹅游行

#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<stack>
#include<queue>
#include <iomanip>
#include<iostream>
#include<algorithm>
using namespace std ;
const int N=500 ;
const int M=100000 ;
const int inf=1<<30 ;
struct node
{
    int u ,v,c,next;
}edge[M] ;

struct node1
{
    int n,m ;
    double x,y;
}e[M] ;

int head[N],dis[N],gap[N],cur[N],pre[N] ;
int top , s,t,sum,n,nv;
double d ;

double Dis(int i,int j)  
{  
    return sqrt(1.0*(e[i].x-e[j].x)*(e[i].x-e[j].x)+(e[i].y-e[j].y)*(e[i].y-e[j].y));  
}  

void add(int u ,int v,int c)     
{    
    edge[top].u=u;    
    edge[top].v=v;    
    edge[top].c=c;    
    edge[top].next=head[u];    
    head[u]=top++;    
    edge[top].u=v;    
    edge[top].v=u;    
    edge[top].c=0;    
    edge[top].next=head[v];    
    head[v]=top++;    
}    

int sap()    
{    
    memset(dis,0,sizeof(dis));    
    memset(gap,0,sizeof(gap));    
    int u,v,minflow=inf,flow=0;    
    for(int i = 0 ; i <=nv ; i++)  cur[i]=head[i] ;    
    u=pre[s]=s;    
    gap[s]=nv;    
    while(dis[s] <= nv )    
    {    
            loop :    
               for(int &j=cur[u] ; j!=-1 ; j=edge[j].next)                   
               {    
                     v=edge[j].v ;    
                     if(edge[j].c > 0 && dis[u] == dis[v] +1 )    
                     {    
                              minflow = min(minflow ,edge[j].c) ;    
                              pre[v]=u;    
                              u=v ;    
                          if(v==t)    
                          {      
                                for( u =pre[v] ; v!=s ;v=u,u=pre[u])    
                                      {    
                                            edge[cur[u]].c -= minflow ;     
                                            edge[cur[u]^1].c += minflow ;    
                                      }     
                                flow += minflow ;    
                                minflow = inf ;    
                          }    
                         goto loop ;    
                     }    
               }    
           int mindis=nv ;    
           for(int i = head[u] ; i!=-1 ; i=edge[i].next)    
           {    
                  v=edge[i].v ;    
                  if(edge[i].c > 0 && dis[v] < mindis)    
                  {    
                       mindis = dis[v] ;    
                       cur[u]=i ;           
                 }    
           }    
          if(--gap[dis[u]]==0) break ;    
          gap[ dis[u] = mindis +1 ]++  ;    
          u=pre[u] ;    
    }    
    return flow ;    
}    



void make(int mid)
{
    memset(head,-1,sizeof(head)) ;
    top = 0 ;
    s=0,t=2*n+1 ,nv=t+1 ;
    for(int i = 1 ; i <= n ; i++)
     {
          add(s,i,e[i].n) ;  //源点连冰块 
         if(i==mid)  //聚集地之间流量没有来限制 
            add(i,i+n,inf) ; 
         else add(i,i+n,e[i].m) ;//限制企鹅数量 
     } 
    for(int i = 1 ; i <= n ;i++ )
      for(int j = i+1; j <= n ; j++)
       {
           if( Dis(i,j) <= d ) //i,j冰块可以互相到达 
             {
               add(i+n,j,inf) ,add(j+n,i,inf)   ;//互相可以跳上去 
            }
       }

} 

int main()
{
    int tt ,f[200];
    scanf("%d",&tt) ;
    while(tt--)
    {
          scanf("%d%lf",&n,&d) ;
          sum = 0;
          for(int i = 1 ; i <= n ; i++)
          {
              scanf("%lf%lf%d%d",&e[i].x,&e[i].y,&e[i].n,&e[i].m) ;
              sum += e[i].n ;
          }
          int k = 0 ;
          for(int i = 1 ; i <= n ; i++)
          {
                make(i) ;
                add(i+n,t,inf) ;  //聚集地到汇点连边 
              if(sap()==sum)   //i冰块可以作为聚集地 
              {
                   f[k++]=i-1 ;
              }
          }
         if(k==0)
            printf("-1\n") ;
          else
          {
                printf("%d",f[0]) ;
                for(int  i = 1 ; i < k ; i++)
                   printf(" %d",f[i]) ;
                 puts("") ;  
          }  

    }
    return 0 ;
} 



#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1005,M=1e6,INF=1e9;
int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int n,a[N],f[N],g[N],s,t,l;
void dp(){
    for(int i=1;i<=n;i++) g[i]=INF;
    for(int i=1;i<=n;i++){
        int k=upper_bound(g+1,g+1+n,a[i])-g;
        f[i]=k;
        g[k]=a[i];
        l=max(l,f[i]);
    }
}
struct edge{
    int v,ne,c,f;
}e[M<<1];
int cnt,h[N];
inline void ins(int u,int v,int c){
    cnt++;
    e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt;
    cnt++;
    e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt;
}
void build(){
    cnt=0;
    memset(h,0,sizeof(h));
    for(int i=1;i<=n;i++){
        if(f[i]==1) ins(s,i,1);
        ins(i,i+n,1);
        if(f[i]==l) ins(i+n,t,1);
        for(int j=1;j<i;j++) if(a[j]<=a[i]&&f[j]+1==f[i]) ins(j+n,i,1);
    }
}
void build2(){
    cnt=0;
    memset(h,0,sizeof(h));
    for(int i=1;i<=n;i++){
        if(i==1||i==n){
            if(f[i]==1) ins(s,i,INF);
            ins(i,i+n,INF);
            if(f[i]==l) ins(i+n,t,INF);
        }else{
            if(f[i]==1) ins(s,i,1);
            ins(i,i+n,1);
            if(f[i]==l) ins(i+n,t,1);
        }
        for(int j=1;j<i;j++) if(a[j]<=a[i]&&f[j]+1==f[i]) ins(j+n,i,1);
    }
}
int vis[N],d[N],q[N],head=1,tail=1;
bool bfs(){
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    head=tail=1;
    q[tail++]=s;d[s]=0;vis[s]=1;
    while(head!=tail){
        int u=q[head++];
        for(int i=h[u];i;i=e[i].ne){
            int v=e[i].v;
            if(!vis[v]&&e[i].c>e[i].f){
                vis[v]=1;d[v]=d[u]+1;
                q[tail++]=v;
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int cur[N];
int dfs(int u,int a){
    if(u==t||a==0) return a;
    int flow=0,f;
    for(int &i=cur[u];i;i=e[i].ne){
        int v=e[i].v;
        if(d[v]==d[u]+1&&(f=dfs(v,min(a,e[i].c-e[i].f)))>0){
            flow+=f;
            e[i].f+=f;
            e[((i-1)^1)+1].f-=f;
            a-=f;
            if(a==0) break;
        }
    }
    return flow;
}
int dinic(){
    int flow=0;
    while(bfs()){//cout<<"p";
        for(int i=s;i<=t;i++) cur[i]=h[i];
        flow+=dfs(s,INF);
    }
    return flow;
}
int main(){
    n=read();s=1;t=n+n+1;
    for(int i=1;i<=n;i++) a[i]=read();
    dp();printf("%d\n",l);
    if(l==1) {printf("%d\n%d",n,n);return 0;}
    build();
    printf("%d\n",dinic());
    build2();
    printf("%d",dinic());
}


活动打卡代码 AcWing 2187. 星际转移问题

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f,M=1000005;
int n,m,k,s,t,tot=1,ans,mx;
int f[100],p[100],g[100][100],num[100];//这里不开这么大第二个点会RE,不知道为什么
int ne[M],to[M],h[M],flow[M],lev[M],q[M];
int find(int x) {
    if(f[x]==x) return x;
    f[x]=find(f[x]);return f[x];
}
void uni(int x,int y) {//并查集的连接操作
    x=find(x),y=find(y);
    if(x!=y) f[x]=y;
}
void add(int x,int y,int z) {
    to[++tot]=y,ne[tot]=h[x],h[x]=tot,flow[tot]=z;
    to[++tot]=x,ne[tot]=h[y],h[y]=tot,flow[tot]=0;
}
int dfs(int x,int liu) {
    if(x==t) return liu;
    int kl,sum=0;
    for(int i=h[x];i;i=ne[i])
        if(flow[i]>0&&lev[to[i]]==lev[x]+1) {
        kl=dfs(to[i],min(flow[i],liu-sum));
        sum+=kl,flow[i]-=kl,flow[i^1]+=kl;
        if(sum==liu) return sum;
    }
    return sum;
}
int bfs() {
    for(int i=1;i<=ans*(n+1);++i) lev[i]=0;
    int he=1,ta=1,x;lev[t]=0,q[1]=s;
    while(he<=ta) {
        x=q[he],++he;
        if(x==t) return 1;
        for(int i=h[x];i;i=ne[i])
            if(flow[i]>0&&!lev[to[i]])
            lev[to[i]]=lev[x]+1,q[++ta]=to[i];
    }
    return 0;
}
int main()
{
    int x,y;
    scanf("%d%d%d",&n,&m,&k);
    s=0,t=M-2;
    for(int i=1;i<=n+2;++i) f[i]=i;
    for(int i=1;i<=m;++i) {
        scanf("%d%d",&p[i],&num[i]);
        for(int j=0;j<num[i];++j) {
            scanf("%d",&g[i][j]);
            if(g[i][j]==0) g[i][j]=n+1;
            if(g[i][j]==-1) g[i][j]=n+2;
            if(j!=0) uni(g[i][j-1],g[i][j]);
        }
    }
    if(find(n+1)!=find(n+2)) {puts("0");return 0;}//如果没有转移方案
    for(ans=1;;++ans) {//枚举答案
        add(s,(ans-1)*(n+1)+n+1,inf);//n+1是地球,汇点是月球。向地球连inf的边
        for(int i=1;i<=m;++i) {
            x=(ans-1)%num[i],y=ans%num[i];
            if(g[i][x]==n+2) x=t;
            else x=(ans-1)*(n+1)+g[i][x];
            if(g[i][y]==n+2) y=t;
            else y=ans*(n+1)+g[i][y];
            add(x,y,p[i]);//一艘飞船一条边
        }
        while(bfs()) mx+=dfs(s,inf);//dinic网络流
        if(mx>=k) {printf("%d\n",ans);return 0;}
        for(int i=1;i<=n+1;++i) add((ans-1)*(n+1)+i,ans*(n+1)+i,inf);//时间间的转移
    }
    return 0;
}