首页 > 其他分享 >ASC 04 题解

ASC 04 题解

时间：2022-10-24 18:00:25浏览次数：47  
标签：return 04 int 题解 ll ASC MAXN double define


A

求最小割方案是否唯一

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair 
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
#define MAXN (4000*2+100)
#define MAXM (60000*2+10)
int n,k;
class tar{
public:
    vi G[MAXN],G2[MAXN];
    int pre[MAXN],lowlink[MAXN],sccno[MAXN],dfs_clock,scc_cnt;
    stack<int> S; 
    void dfs(int u) {
        pre[u] = lowlink[u] = ++dfs_clock;
        S.push(u);
        int sz=SI(G[u]);
        Rep(i,sz) {
            int v=G[u][i];
            if (!pre[v]) {
                dfs(v);
                lowlink[u]=min(lowlink[u],lowlink[v]);
            } else if (!sccno[v]) {
                lowlink[u]=min(lowlink[u],pre[v]);
            } 
        } 
        if (lowlink[u]==pre[u]) {
            scc_cnt++;  
            while(1) {
                int x=S.top();S.pop();
                sccno[x]=scc_cnt;
                if (x==u) break;  
            } 
        }       
    } 
    void find_scc(int n) {
        dfs_clock = scc_cnt = 0;
        MEM(sccno) 
        MEM(pre)
        Rep(i,n) if (!pre[i]) dfs(i);
    }
    void mem(int n) {
        Rep(i,n) G[i].clear(),G2[i].clear();
    }
}S2;
class Max_flow  //dinic+当前弧优化   
{    
public:    
    int n,t;    
    int q[MAXN];    
    ll weight[MAXM];
    int edge[MAXM],Next[MAXM],Pre[MAXN],size;    
    void addedge(int u,int v,int w)      
    {      
        edge[++size]=v;      
        weight[size]=w;      
        Next[size]=Pre[u];      
        Pre[u]=size;      
    }      
    void addedge2(int u,int v,int w){addedge(u,v,w),addedge(v,u,w);}     
    bool b[MAXN];    
    ll d[MAXN];    
    bool SPFA(int s,int t)      
    {      
        MEMI(d)
        MEM(b)    
        d[q[1]=s]=0;b[s]=1;      
        int head=1,tail=1;      
        while (head<=tail)      
        {      
            int now=q[head++];      
            Forp(now)      
            {      
                int &v=edge[p];      
                if (weight[p]&&!b[v])      
                {      
                    d[v]=d[now]+1;      
                    b[v]=1,q[++tail]=v;      
                }      
            }          
        }      
        return b[t];      
    }     
    int iter[MAXN];  
    int dfs(int x,ll f)  
    {  
        if (x==t) return f;  
        Forpiter(x)  
        {  
            int v=edge[p];  
            if (weight[p]&&d[x]<d[v])  
            {  
                  int nowflow=dfs(v,min(weight[p],f));  
                  if (nowflow)  
                  {  
                    weight[p]-=nowflow;  
                    weight[p^1]+=nowflow;  
                    return nowflow;  
                  }  
            }  
        }  
        return 0;  
    }  
    ll max_flow(int s,int t)  
    {  
        (*this).t=t;
        ll flow=0;  
        while(SPFA(s,t))  
        {  
            For(i,n) iter[i]=Pre[i];  
            ll f;  
            while (f=dfs(s,INF))  
                flow+=f;   
        }  
        return flow;  
    }   
    void mem(int n)    
    {    
        (*this).n=n;  
        size=1;    
        MEM(Pre)   
    }
    void init(int n) {
        For(i,n) {
            Forp(i) {
                int v=edge[p];  
                // cout<<i<<' '<<v<<' '<<weight[p]<<endl;
                if (!weight[p]) {
                    // if (i<=n1&&v>n1&&v<=n1+m1) {
                    //     ::b[i][v-n1]=1;
                    //     // cout<<i<<' '<<v-n1<<endl;
                    // }
                }
                else S2.G[i-1].pb(v-1),S2.G2[i-1].pb(p);
            }
        }
    }   
}S;  
struct {
    int u,v;
}e[MAXM];
int main() {
    freopen("attack.in","r",stdin);
    freopen("attack.out","w",stdout);
    int n,m,s,t;
    n=read(),m=read(),s=read(),t=read();
    S.mem(n);
    For(i,m) {
        int u=read(),v=read(),w=read();
        S.addedge2(u,v,w);
        e[i].u=u,e[i].v=v;
    }
    ll p=S.max_flow(s,t);
    S.init(n);

    S2.find_scc(n);
    s--,t--;
    bool fl=0;
    For(i,m) {
        e[i].u--,e[i].v--;
        if (S.weight[i*2]) ;
        else if (S2.sccno[e[i].u]==S2.sccno[s] && S2.sccno[e[i].v]==S2.sccno[t]) ;
        else if (S2.sccno[e[i].u]!=S2.sccno[e[i].v]) fl=1;
    }
    S2.mem(n);
    puts(fl?"AMBIGUOUS":"UNIQUE");
    return 0;
}

C

已知n个圆（n<=50)，求平面被分割成了几份。
欧拉定理：点数-边数+面数=2（平面图连通）
注意这题对精度要求较高，求圆交点避开三角函数，用sqrt代替

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
//#define double __float128
//#define ld __float128
typedef long long ll;
typedef long double ld;
ld sqr(ld a){return a*a;}
const double eps=1e-8;
int dcmp(double x) {
    if (max(x,-x)<eps) return 0; else return x<0 ? -1 : 1; 
}
ld PI = 3.141592653589793238462643383;
class P{
public:
    double x,y;
    P(double x=0,double y=0):x(x),y(y){}
    friend ld dis2(P A,P B){return sqr(A.x-B.x)+sqr(A.y-B.y);   }
    friend ld Dot(P A,P B) {return A.x*B.x+A.y*B.y; }
//    friend ld Length(P A) {return sqrt(Dot(A,A)); }
//    friend ld Angle(P A,P B) {
//        if (dcmp(Dot(A,A))==0||dcmp(Dot(B,B))==0||dcmp(Dot(A-B,A-B))==0) return 0;
//        return acos(max((ld)-1.0, min((ld)1.0, Dot(A,B) / Length(A) / Length(B) )) ); 
//    }
    P rotate90()const{ return{ -y, x }; }

    friend P operator- (P A,P B) { return P(A.x-B.x,A.y-B.y); }
    friend P operator+ (P A,P B) { return P(A.x+B.x,A.y+B.y); }
    friend P operator* (P A,double p) { return P(A.x*p,A.y*p); }
    friend P operator/ (P A,double p) { return P(A.x/p,A.y/p); }
    friend bool operator< (const P& a,const P& b) {return dcmp(a.x-b.x)<0 ||(dcmp(a.x-b.x)==0&& dcmp(a.y-b.y)<0 );}

}; 
P read_point() {
    P a;
    scanf("%lf%lf",&a.x,&a.y);
    return a;   
} 
bool operator==(const P& a,const P& b) {
    return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y) == 0;
} 
typedef P V;

/*欧拉公式： V+F-E=2 
V-点数 F面数 E边数 */
double Cos(double x) {
    return 1-x*x/2+x*x*x*x/4/3/2-x*x*x*x*x*x/6/5/4/3/2;
}
double Sin(double x) {
    return x/1-x*x*x/3/2+x*x*x*x*x/5/4/3/2/1;
}
struct C{
    P c;
    double r,x,y;
    C(){}
    C(P c,double r=0):c(c),r(r),x(c.x),y(c.y){}
    P point(double a) {
        return P(c.x+Cos(a)*r,c.y+Sin(a)*r);
    }

};
double angle(V v) {return atan2(v.y,v.x);}
int getCircleCircleIntersection(C C1,C C2,vector<P>& sol) {
    double d = sqrt(dis2(C1.c,C2.c));
    if (dcmp(d)==0) {
        if (dcmp(C1.r - C2.r)==0) return -1; //2圆重合 
        return 0;
    }
    if (dcmp(C1.r+C2.r-d)<0) return 0;
    if (dcmp(max(C2.r-C1.r,C1.r-C2.r)-d)>0) return 0;
    d=dis2(C1.c,C2.c);
    double t1 = (C1.r*C1.r - C2.r*C2.r) / (2 * d) + 0.5;
    double t2 = C1.r*C1.r / d - t1*t1;
    t2 = (dcmp(t2)<=0) ? (0): sqrt(max(0.0,t2));
    P foot = C1.c + (C2.c - C1.c)*t1;
    P p1 = foot + (C2.c - C1.c).rotate90() * t2;
    P p2 = foot * 2 - p1;
    sol.pb(p1);
    if (p1==p2) return 1;
    sol.pb(p2);
    return 2; 
}
//void circleCircleIntersectPoint(const Point& o1, double r1, const Point& o2, double r2, Point& ret1, Point& ret2)
//{
//  double d2 = o1.dis2(o2);
//  double t1 = (r1*r1 - r2*r2) / (2 * d2) + 0.5;
//  double t2 = r1*r1 / d2 - t1*t1;
//  t2 = LEQ(t2, 0) ? 0 : sqrt(t2);
//  Point foot = o1 + (o2 - o1)*t1;
//  ret1 = foot + (o2 - o1).rotate90()*t2;
//  ret2 = foot * 2 - ret1;
//}

int n;
#define MAXN (102345)
class bingchaji
{
public:
    int father[MAXN],n,cnt;
    void mem(int _n)
    {
        n=cnt=_n;
        For(i,n) father[i]=i;
    }
    int getfather(int x) 
    {
        if (father[x]==x) return x;

        return father[x]=getfather(father[x]);
    }
    void unite(int x,int y)
    {
        x=getfather(x);
        y=getfather(y);
        if (x^y) {
            --cnt;
            father[x]=y;
        }
    }
    bool same(int x,int y)
    {
        return getfather(x)==getfather(y);
    }
}S;

void print(double a) {
    printf("%.6lf",a); 
}
void print(P p) {
    printf("(%.6lf,%.6lf)",p.x,p.y);
}
template<class T>
void print(vector<T> v) {
    sort(v.begin(),v.end());
    putchar('[');
    int n=v.size();
    Rep(i,n) {
        print(v[i]);
        if (i<n-1) putchar(','); 
    }
    puts("]");
}
void CircleUnion(C c[],int n) {
    ll dotsum=0,edgesum=0; 
    vector<P> Sol;
    S.mem(n);
    Rep(i,n) {
        int cnt = 0;
        vector<P> sol; sol.clear();

        Rep(j,n) if (i^j) {
            int sz=SI(sol);
            getCircleCircleIntersection(c[i],c[j],sol);
            getCircleCircleIntersection(c[i],c[j],Sol);

            sz=SI(sol)-sz;
            if (sz) {
                S.unite(i+1,j+1);
            }

        }
        sort(ALL(sol));
        sol.erase(unique(ALL(sol)),sol.end());
        edgesum+=SI(sol);
    }
    sort(ALL(Sol));
    Sol.erase(unique(ALL(Sol)),Sol.end());
    dotsum=SI(Sol);
    int p=S.cnt;
    cout<<-dotsum+edgesum+2*p-p+1<<endl;
}
C cir[MAXN];
int main()
{

  freopen("circles.in","r",stdin);
  freopen("circles.out","w",stdout);
//  freopen("C.in","r",stdin);
    while(cin>>n) {
        Rep(i,n) {
            ll x,y,r;
            cin>>x>>y>>r;
            cir[i].x=x,cir[i].y=y,cir[i].r=r;
            cir[i].c=P(x,y);
        }
        CircleUnion(cir,n);
    }
    return 0;
}

D

输入一个单纯形问题，按指定格式输出它的对偶问题。

#include<bits/stdc++.h> 
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %lld\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
#define MAXN (210)
char s[10000];
bool is_min;
int a[210],n,m;
int sig[MAXN];
isdig(char c) {
    return isdigit(c)|c=='+'|c=='-';
} 
int getint(int &i) {
    int x=0,f=1;
    if (s[i]=='x') {
        ++i;return 1;
    }
    if (!isdigit(s[i])) {
        if (s[i]=='+') i++;
        else if (s[i]=='-') f=-1,++i;
    }
    bool fl=0;
    while(isdigit(s[i])) {
        x=x*10+s[i]-'0'; ++i; fl=1;
    }
    while(!isdig(s[i]) &&s[i]) ++i;
    if (!x&&!fl) x=1;
    return x*f;
}
int f[MAXN][MAXN]={};
void get(vi &v) {
    int l=strlen(s);
    for(int i=0;i<l;) {
        int p=getint(i);
        v.pb(p);
    }
}
void get1() {
    vi v; MEM(a)
    get(v);
    for(int i=0;i<SI(v);i+=2) {
        a[v[i+1]]=v[i];
    }
}
int sig2[MAXN];
void getsig(int &si) {
    char *c=strchr(s,'>');
    if (NULL!=strchr(s,'>')) si=1;
    else if (NULL!=strchr(s,'<')) si=-1;
    else si=0;
}
int p[MAXN];
void pri(int a[]=p) {
    bool fl=0;
    For(i,m) if (a[i]) {
        if (a[i]==1) {
            if (fl) putchar('+');
        }
        else if (a[i]==-1) putchar('-');
        else {
            if (fl&&a[i]>0) putchar('+');
            cout<<a[i];
        }
        putchar('y');
        cout<<i;
        fl=1;
    }
    if(!fl) putchar('0');
}
int c[MAXN];
int main()
{
//  freopen("D.in","r",stdin);
    freopen("dual.in","r",stdin);
    freopen("dual.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    scanf("%s",s);
    if (strcmp(s,"min")==0) is_min=1;else is_min=0;
    scanf("%s\n",s);
    get1();
    scanf("%s\n",s);
    For(i,n) {
        cin.getline(s,5000);
        getsig(sig[i]);
    }
    scanf("%s\n",s);
    For(i,m) {
        cin.getline(s,5000);
        getsig(sig2[i]);
        vi v;
        get(v);
        int sz=SI(v);
        for(int j=0;j<sz-2;j+=2) {
            f[i][v[j+1]]=v[j];
        }
        c[i]=v[sz-1];
//      Rep(i,sz) cout<<v[i] <<' ';puts("");
    }
//  PRi2D(f,m,n)

    printf("%d %d\n",m,n);
    if (is_min) cout<<"max ";else cout<<"min ";

//  PRi(c,m)/
    pri(c);
    puts("");
    puts("with");
    For(i,m) {
        if (is_min) {
            if (sig2[i]==1) printf("y%d>=0\n",i);
            else if (sig2[i]==-1) printf("y%d<=0\n",i);
            else printf("y%d arbitary\n",i);
        } else {
            if (sig2[i]==-1) printf("y%d>=0\n",i);
            else if (sig2[i]==1) printf("y%d<=0\n",i);
            else printf("y%d arbitary\n",i);
        }
    }
    puts("under");
    For(i,n) {
        For(j,m) p[j]=f[j][i];
        pri();
        if (!is_min) {
            if (sig[i]==1) printf(">=");
            else if (sig[i]==-1) printf("<=");
            else printf("="); 
        } else {
            if (sig[i]==-1) printf(">=");
            else if (sig[i]==1) printf("<=");
            else printf("="); 
        }
        cout<<a[i];
        puts(""); 
    }
    return 0;
}


标签：return,04,int,题解,ll,ASC,MAXN,double,define
From： https://blog.51cto.com/u_15724837/5790765

相关文章

  • leetcode-504-easy
    Base7Givenanintegernum,returnastringofitsbase7representation.Example1:Input:num=100Output:"202"Example2:Input:num=-7Output:"-10......
  • 面试 个人摸底监测 考察JavaScript基础 （第三天）
    01，如何开启JS严格模式？JS严格模式有什么特点？两种方式全局开启在js开头加上'usestrict'局部开启，在作用域开头加上functionfn(){'usestrict'}特点：1，全局变量必须......
  • JavaScript 设计模式之策略模式
    什么是设计模式？为什么需要学习设计模式？学习设计模式的目的是：为了代码可重用性、让代码更容易被他人理解、保证代码可靠性。设计模式使代码编写真正工程化；设计模式是软件工......
  • DASCTF X GFCTF 2022十月挑战赛 pwn wp
    目录1r()p21!5!3magic_book随便做了下。1r()p利用如下几个gadgets构造即可：#控制rax后任意地址写.text:000000000040115Amovrsi,rax......
  • 周日1040C++班级2022-10-23 初始C++
    初识C++一、C++程序框架C++的程序是有一个大的框架的，我们需要使用include去让我们的程序包含C++的头文件iostream；并且在下一行还有usingnamespacestd去使用C++的标准名......
  • hihoCoder挑战赛31 题解
    题目1:Numbers时间限制:8000ms单点时限:1000ms内存限制:256MB描述给定n个整数常数c[1],c[2],…,c[n]和一个整数k。现在需要给2k个整数变量x[1],x[2],…,x[k......
  • JavaScript对象-Date、Math
    JavaScript对象-Date<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>Date对象</title><script>/*Date:......
  • 616Javascript_语法_练习_99乘法表 and
    练习9*9乘法表<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>99乘法表</title><style>td{border:1pxs......
  • "Ascend.Net" Windows Forms Controls
    在微软的开源网站上http://www.codeplex.com有一个WinformControl项目Ascend.NET,非常不错.做Winform程序的兄弟可以关注一下.在微软的开源网站上......
  • JavaScript_对象-Function、Array
    JavaScript_对象-Function<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>Function对象</title><script>/*......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99