贼惨 130/186

B Black Widow

简单题

#include 
      
       const long long mod = 1e9+7;const double ex = 1e-10;#define inf 0x3f3f3f3fusing namespace std;map 
       
         M;int a[1010];int b[100010];int main(){    int N;    scanf("%d",&N);    int t = 0;    for (int i = 1; i<=N;i++){        scanf("%d",&a[i]);        t = max(t,a[i]);        for (int j = 1; j*j<=a[i];j++)            if (a[i]%j==0) {                    b[j] = 1;                if (a[i]/j > 100000)M[a[i]/j]++;                else b[a[i]/j] = 1;            }    }    for (int i = 2 ;i<=1000000001 ;i++)        if ((i<=100000&&b[i]==0)||(i>100000&&M[i]==0))        {            printf("%d\n",i);            return 0;        }    return 0;}
       
      

C Chitauri

海盗分金，按照海盗分金的贪心策略递推的求。

#include 
      
       using namespace std;int n,k;int vis[3005],money[3005],last;int main(){    scanf("%d%d",&n,&k);    money[1] = k;    last = 1;    for (int i=2;i<=n;++i) {            int cnt = 0;            int gg = 0;            for (int j = 1;j<=i-1;j++){                if (money[j] == 0)                    cnt++;                if (money[j] == -1)                    gg++;            }            if (2*(min(cnt,k)+gg+1) < i ) {                money[i] = -1;                continue;            }            last = i;            int tk=k;            if (k-((i+1)/2 - gg -1) > 0) money[i] =k-((i+1)/2 - gg -1),tk-=money[i];            for (int j=i-1;j>=1;--j) {                if (money[j]==-1)                    money[j]=0;                else if (money[j]==0) {                    if (tk>0) {                        money[j]=1;                        --tk;                    }                } else                    money[j]=0;            }        }            for (int z=n;z>=1;--z)            printf("%d%c",money[z],z==1?'\n':' ');    return 0;}
      

 D Dr. Banner

简单DP

#include 
      
       using namespace std;const long long mod=1e9+7;int n;long long dp[21][100005];int main(){    scanf("%d",&n);    dp[0][n]=1;    for (int i=1;i<=20;++i) {        for (int j=1;j<=n;++j)            dp[i-1][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;        for (int j=1;j*2<=n;++j)            dp[i][j]=(dp[i-1][n]-dp[i-1][2*j-1]+mod)%mod;    }    long long res=0;    for (int i=0;i<=20;++i)        res=(res+dp[i][n])%mod;    cout<
       
        <
       
      

E Egocentric Loki (补)

题目很长，其实就是枚举每个三角形，判断是否有点处于这个三角形和它的外接圆之间。

精度的要求还是比较低的，就是输入数据范围有误，，心态崩了。

#include 
      
       using namespace std;const long double eps=1e-8;int sgn ( long double x ) {    return ( x > eps ) - ( x < -eps ) ;}struct Point{    long double x,y;    Point(){}    Point(long double _x,long double _y){        x=_x;y=_y;    }    Point operator +(const Point &b)const{        return Point(x+b.x,y+b.y);    }    Point operator /(const long double &k)const{        return Point(x/k,y/k);    }    Point operator -(const Point &b)const {        return Point(x-b.x,y-b.y);    }    Point operator *(const long double &rhs)const{        return Point(x*rhs,y*rhs);    }    long double operator ^(const Point &b) const {        return x*b.y-y*b.x;    }    long double distance(Point p) {        return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y);    }    Point rotleft(){        return Point(-y,x);    }};struct Line{    Point s,e;    Line(){}    Line(Point _s,Point _e){        s=_s;        e=_e;    }    /*    Point line_intersection (Line v) {//( P a , P b , P p , P q  ) {        double U = cross ( p - a , q - p ) ;        double D = cross ( b - a , q - p ) ;        return a + ( b - a ) * ( U / D ) ;    }    */    Point crosspoint(Line v) {        long double U=(v.s-s)^(v.e-v.s);        long double D=(e-s)^(v.e-v.s);        return s+(e-s)*(U/D);    }};struct Circle{    Point p;long double r;    Circle(){}    Circle(Point a,Point b,Point c){        Line u=Line((a+b)/2.0,(a+b)/2.0+(a-b).rotleft());        Line v=Line((b+c)/2.0,(b+c)/2.0+(c-b).rotleft());        p=u.crosspoint(v);        r=p.distance(a);    }    int relation(Point b){        long double dst=b.distance(p);        if(sgn(dst-r)<0) return 2;        else if(sgn(dst-r)==0) return 1;        return 0;    }};inline double area(double x1,double y1,double x2,double y2,double x,double y) {    double X1=x1-x,Y1=y1-y,X2=x2-x,Y2=y2-y;    return fabs(X1*Y2-X2*Y1);}inline bool intriangle(double x1,double y1,double x2,double y2,double x3,double y3,double x,double y) {    int flag=sgn(area(x1,y1,x2,y2,x3,y3)-area(x1,y1,x2,y2,x,y)-area(x1,y1,x3,y3,x,y)-area(x2,y2,x3,y3,x,y));    return flag==0;}int n;long double xx1[10010],yy1[10010],xx2[10010],yy2[10010],xx3[10010],yy3[10010];int main(){    while (scanf("%d",&n)==1) {        for(int i=1;i<=n;i++)            cin>>xx1[i]>>yy1[i]>>xx2[i]>>yy2[i]>>xx3[i]>>yy3[i];        int flag=0;        for(int i=1;i<=n;i++) {            Circle now=Circle(Point(xx1[i],yy1[i]),Point(xx2[i],yy2[i]),Point(xx3[i],yy3[i]));            //cout<
       
        <<" "<
        
         <<" "<
         
          <
          
           =1))                    flag=1;                if(!intriangle(xx1[i],yy1[i],xx2[i],yy2[i],xx3[i],yy3[i],xx2[j],yy2[j])&&(now.relation(Point(xx2[j],yy2[j]))>=1))                    flag=1;                if(!intriangle(xx1[i],yy1[i],xx2[i],yy2[i],xx3[i],yy3[i],xx3[j],yy3[j])&&(now.relation(Point(xx3[j],yy3[j]))>=1))                    flag=1;                if(flag)                    break;            }            if(flag)                break;        }        if(flag) printf("NO\n");        else printf("YES\n");    }    return 0;}
          
         
        
       
      

 

F Fury

缩点 ，然后DAG上贪心

#include 
      
       const long long mod = 1e9+7;const double ex = 1e-10;#define REP(i,x,y) for(int i=x;i<(y);i++)#define RREP(i,x,y) for(int i=x;i>(y);i--)#define inf 0x3f3f3f3f#define maxn 310using namespace std;int n,m,pre[maxn],low[maxn],sccno[maxn],dfs_clock,scc_cnt;vector
       
        e[maxn];stack
        
         S;void dfs(int st) {    pre[st]=low[st]=(++dfs_clock);    S.push(st);    REP(i,0,e[st].size()) {        int nxt=e[st][i];        if(!pre[nxt]) {            dfs(nxt);            low[st]=min(low[st],low[nxt]);        }        else if(!sccno[nxt]) {            low[st]=min(low[st],pre[nxt]);        }    }    if(low[st]==pre[st]) {        scc_cnt++;        while(1) {            int now=S.top();S.pop();            sccno[now]=scc_cnt;            if(now==st) break;        }    }}void Tarjan() {    dfs_clock=scc_cnt=0;    memset(sccno,0,sizeof(sccno));    memset(pre,0,sizeof(pre));    for(int i=1;i<=n;i++) if(!pre[i]) dfs(i);}struct edge{    int v,f,u,vv;    edge(){}    edge(int _v,int _f,int u,int v):v(_v),f(_f),u(u),vv(v){}};vector
         
          DAG[maxn];int col[maxn],DAG_cnt;void gao() {    REP(i,1,n+1) {        int u=sccno[i];        REP(j,0,e[i].size()) {            int v=sccno[e[i][j]];            if(v==u) continue;            DAG_cnt++;            DAG[u].push_back(edge(v,0,i,e[i][j]));        }    }}int num[maxn];int dfs2(int rt) {    num[rt]++;    for(int i=0;i
          
           =1) {num[nxt]++;continue;}        dfs2(nxt);    }}vector
           
            SCC[maxn];typedef pair
            
              pii;vector
             
              Ans;int main(){ scanf("%d %d",&n,&m); REP(i,1,m+1) { int u,v;scanf("%d %d",&u,&v); e[u].push_back(v); } Tarjan(); int ans=0; for(int i=1;i<=n;i++) SCC[sccno[i]].push_back(i); for(int i=1;i<=scc_cnt;i++){ if(SCC[i].size()==1) continue; for(int j=0;j
              
               1) ans+=col[i]; gao(); for(int i=1;i<=scc_cnt;i++) { for(int i=1;i<=scc_cnt;i++) num[i]=0; dfs2(i); for(int j=0;j
              
             
            
           
          
         
        
       
      

G Groot

签到

#include 
      
       const long long mod = 1e9+7;const double ex = 1e-10;#define inf 0x3f3f3f3fusing namespace std;int main(){    string  s;    cin >> s ;    cin >> s ;    cin >> s ;    if (s.length() == 5) puts("Pfff");        else    {        cout <<'W';        for (int i = 1; i<=s.length()-5;i++) cout <<'o';        puts("w");    }    return 0;}
      

J 待补