牛客练习赛12

https://www.nowcoder.net/acm/contest/68/A思路:判断一下顺时针角度大还是逆时针角度大,怎么写都可以吧,pi=acos(-1)还是要知道的
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
double pi=acos(-1);
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        double a,b;
        cin>>a>>b;
        double n=a-b;
        while(n<0)n+=2*pi;
        if(n>pi){
            printf("counterclockwisen");
        }else{
            printf("clockwisen");
        }
    }
    return 0;
}
View Codehttps://www.nowcoder.net/acm/contest/68/B思路:经典的bfs题目改了改,首先第一次从S点bfs,不能经过D和W,第二次已经知道了从S到K的最短距离,从K点bfs一次,不能经过W,能经过D,答案就是S直接到E的距离和S到K再到E的距离取最小
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
#include<queue>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
char a[600][600];
int S[2],D[2],E[2],K[2];
int d[600][600];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%s",a[i]+1);
        for(int j=1;j<=m;j++){
            if(a[i][j]=='D'){
                D[0]=i;
                D[1]=j;
            }else if(a[i][j]=='S'){
                S[0]=i;
                S[1]=j;
            }else if(a[i][j]=='E'){
                E[0]=i;
                E[1]=j;
            }else if(a[i][j]=='K'){
                K[0]=i;
                K[1]=j;
            }
        }
    }
    memset(d,127,sizeof(d));
    queue<pair<int,int> > q;
    q.push({S[0],S[1]});
    d[S[0]][S[1]]=0;
    while(q.size()){
        //dbg(q.size());
        int x=q.front().fi;
        int y=q.front().se;
        q.pop();
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                if(i*j==0 && j!=i){
                    d[x][y]=min(d[x][y],d[x+i][y+j]+1);
                    if(a[x+i][y+j]!='W' && a[x+i][y+j]!='D' && d[x+i][y+j]==d[0][0]){
                        q.push({x+i,y+j});
                    }
                }
            }
        }
    }
    long long res=d[E[0]][E[1]];
    long long pre=d[K[0]][K[1]];
    memset(d,127,sizeof(d));
    q.push({K[0],K[1]});
    d[K[0]][K[1]]=0;
    //dbg(K[0]);
    //dbg(K[1]);
    while(q.size()){
        //dbg(q.size());
        int x=q.front().fi;
        int y=q.front().se;
        q.pop();
        for(int i=-1;i<=1;i++){
            for(int j=-1;j<=1;j++){
                if(i*j==0 && j!=i){
                    d[x][y]=min(d[x][y],d[x+i][y+j]+1);
                    if(a[x+i][y+j]!='W' && d[x+i][y+j]==d[0][0]){
                        q.push({x+i,y+j});
                    }
                }
            }
        }
    }
    res=min(res,pre+d[E[0]][E[1]]);
    if(res<1e9){
        cout<<res;
    }else{
        cout<<-1;
    }
    return 0;
}
View Codehttps://www.nowcoder.net/acm/contest/68/C思路:首先做这题肯定得先知道单调栈是什么,考虑两种情况,一种情况是h2h1,同样显然h2==MAX(Li) ,只要找到MAX(Li)所在的一行,上下分别做一次单调栈,每次从两个栈中弹出L最小的那个,不断更新上下界就行了.(我的代码似乎是别人的三倍长 :(
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
#include <stack>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
__int128 h[10000000];
int L[10000000],R[10000000];
void print(__int128 x){
    if(x==0){
        printf("0");
    }else{
        stack<int> s;
        while(x){
            s.push((int)(x%10));
            x/=10;
        }
        while(s.size()){
            printf("%d",s.top());
            s.pop();
        }
    }
    printf("n");
}
int main(){
    int ng,n;
    scanf("%d %d",&ng,&n);
    int sz=0;
    __int128 mxh=-1;
    int mxid=0;
    while(ng--){
        unsigned long long ns,s,a,b,mod;
        cin>>ns>>s>>a>>b>>mod;
        h[++sz]=s;
        if(h[sz]>mxh){
            mxh=h[sz];
            mxid=sz;
        }
        __int128 tmp=s;
        ns--;
        while(ns--){
            tmp=(tmp*a+b)%mod;
            if(tmp==0)tmp=mod;
            h[++sz]=tmp;
            if(h[sz]>mxh){
                mxh=h[sz];
                mxid=sz;
            }
        }
    }

    __int128 res=mxh*n;
    stack<int> l,r;
    for(int i=mxid-1;i>=1;i--){
        while(l.size() && h[i]>=h[l.top()])l.pop();
        l.push(i);
    }
    for(int i=mxid+1;i<=n;i++){
        while(r.size() && h[i]>=h[r.top()])r.pop();
        r.push(i);
    }
    __int128 hh=0;
    __int128 up=0;
    __int128 down=n+1;
    while(l.size()!=0 || r.size()!=0){
        if(l.size()==0){
            int x=r.top();
            hh=max(hh,h[x]);
            r.pop();
            if(r.size()==0){
                down=mxid+1;
            }else{
                down=r.top()+1;
            }
            res=min(res,hh*(-down+n+1+up)+mxh*(down-up-1));
        }else if(r.size()==0){
            int x=l.top();
            hh=max(hh,h[x]);
            l.pop();
            if(l.size()==0){
                up=mxid-1;
            }else{
                up=l.top()-1;
            }
            res=min(res,hh*(-down+n+1+up)+mxh*(down-up-1));
        }else{
            if(h[l.top()]<h[r.top()]){
                int x=l.top();
                hh=max(hh,h[x]);
                l.pop();
                if(l.size()==0){
                    up=mxid-1;
                }else{
                    up=l.top()-1;
                }
                res=min(res,hh*(-down+n+1+up)+mxh*(down-up-1));
            }else{
                int x=r.top();
                hh=max(hh,h[x]);
                r.pop();
                if(r.size()==0){
                    down=mxid+1;
                }else{
                    down=r.top()+1;
                }
                res=min(res,hh*(-down+n+1+up)+mxh*(down-up-1));
            }
        }
    }
    h[0]=h[n+1]=mxh+7;

    for(int i=0;i<=n+1;i++){
        while(l.size() && h[i]>h[l.top()]){
            R[l.top()]=i-1;
            l.pop();
        }
        if(i<=n && i>=1)L[i]=l.top()+1;
        l.push(i);
    }

    for(int i=1;i<=n;i++){
        //printf("%d %d %dn",i,L[i],R[i]);
        res=min(res,h[i]*(R[i]-L[i]+1)+mxh*(n-(R[i]-L[i]+1)));
    }
    print(res);
    return 0;
}
View Codehttps://www.nowcoder.net/acm/contest/68/D思路:没有思路,高斯消元裸题,知道高斯消元是啥这题应该就肯定会做了 (so sad 没接触过高斯消元 :(
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
const int mxn=1e5;
int g[mxn],v[mxn],nxt[mxn],w[mxn],ed=0;
void add(int x,int y,int W){
    v[++ed]=y;
    nxt[ed]=g[x];
    g[x]=ed;
    w[ed]=W;
}
double mt[120][120];
long long sum[120];
int n,m;
const double eps=1e-11;
void guass(){
    for(int i=1;i<=n+1;i++){
        int r=i;
        for(int j=i+1;j<=n+1;j++)if(fabs(mt[j][i])>fabs(mt[r][i]))r=j;
        if(fabs(mt[r][i])<eps)continue;
        if(r!=i)for(int j=i;j<=n+1;j++)swap(mt[i][j],mt[r][j]);
        for(int k=1;k<=n+1;k++)
            if(k!=i)
                for(int j=n+1;j>=i;j--)
                    mt[k][j]-=mt[k][i]/mt[i][i]*mt[i][j];
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        u++,v++;
        sum[u]+=w;
        add(u,v,w);
    }
    for(int i=1;i<=n;i++){
        if(sum[i]==0){
            sum[i]=1;
            add(i,i,1);
        }
    }
    for(int i=1;i<=n;i++){
        mt[i][i]=-1;
    }
    for(int i=1;i<=n+1;i++)mt[n+1][i]=1;
    for(int x=1;x<=n;x++){
        for(int i=g[x];i;i=nxt[i]){
            mt[v[i]][x]+=(double)w[i]/sum[x];
        }
    }
    guass();
    for(int i=1;i<=n;i++){
        if(fabs(mt[i][i])<eps && fabs(mt[i][n+1])>eps){
            printf("Impossiblen");
            return 0;
        }
    }
    if(fabs(mt[n+1][n+1])>eps){
        printf("Impossiblen");
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(fabs(mt[i][i])<eps)printf("%.14fn",0.0);
        else printf("%.14fn",mt[i][n+1]/mt[i][i]);
    }
    return 0;
}
View Codehttps://www.nowcoder.net/acm/contest/68/E思路:这可能是这套题除了A题最水的题目了 :)比赛的时候居然没人过 ,首先一个常识肯定先把b映射成1,2,3...,n的排列,a相应的改变,接下来就是问a通过最小交换次数变成有序吧啦吧啦......经过c,一个常识就是最小交换次数每次肯定交换相邻的逆序数.我们就考虑什么时候a[i]会因为交换而跳出i到a[i]这段范围,假设经过若干次交换a[i]到达了i位置,如果这时候我想让a[i]往左或往右交换一定是 a[i-1]>a[i]>a[i+1] (似乎很显然?脑补一下?),所以其实只要求对于每个a[i]是否存在a[j]>a[i],ji. (地球人应该都会o(n)的做法吧
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
int a[1000010];
int b[1000010];
int posa[1000010];
int al[1000010];
int ar[1000010];
char res[1000010];
namespace IO {
    const int MX = 4e7; //1e7占用内存11000kb
    char buf[MX]; int c, sz;
    void begin() {
        c = 0;
        sz = fread(buf, 1, MX, stdin);
    }
    template<class T>
    inline bool read(T &t) {
        while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
        if(c >= sz) return false;
        bool flag = 0; if(buf[c] == '-') flag = 1, c++;
        for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
        if(flag) t = -t;
        return true;
    }
}
using namespace IO;

int main(){
    begin();
    int n;
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        posa[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        read(b[i]);
        a[posa[b[i]]]=i;
    }
    al[1]=a[1];
    for(int i=2;i<=n;i++){
        al[i]=max(al[i-1],a[i]);
    }
    ar[n]=a[n];
    for(int i=n-1;i>=1;i--){
        ar[i]=min(ar[i+1],a[i]);
    }
    for(int i=1;i<=n;i++){
        if(a[i]<al[i] && a[i]>ar[i]){
            res[b[a[i]]]='1';
        }else{
            res[b[a[i]]]='0';
        }
    }
    res[n+1]='';
    printf("%s",res+1);
    return 0;
}
View Codehttps://www.nowcoder.net/acm/contest/68/F思路:首先把图打出来,吧W打成空格看起来清楚一点然后看看这个图,开开脑洞就会发现,答案其实是(b行a列到a+w-1列联通块个数)+(a列b行到b+h-1行联通块个数)-(b行a列=='B'?1:0),同样还能发现的就是每行连续的B的长度是固定的把一个二维的看起来完全不能做的东西变成了一维的,而且因为图是关于y=x对称的,所以只要写一个求出某行某段联通块个数就行了.具体怎么做就是用这个图递归的性质,把每次询问的复杂度降到log(n),n=max(a+w,b+h)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define pb push_back
#define fi first
#define se second
long long cnt(long long r,long long i,long long l,long long R){
    if(l==1)return 1;
    if(R>r-l/2){
        return cnt(r,i-1,l/2,R);
    }else{
        long long ret=cnt(r-l/2,i-1,l/2,R);
        if(ret==l/2)ret*=2;
        return ret;
    }
}
long long tmp[64];
long long rcnt(long long r,long long i,long long l,long long R,long long C){
    if(C==0)return 0;
    if(l==1)return 1;
    if(tmp[i]!=0 && l==C)return tmp[i];
    if(R>r-l/2){
        if(C==l){
            return tmp[i]=rcnt(r,i-1,l/2,R,l/2);
        }else if(C<=l/2){
            return 0;
        }else{
            return rcnt(r,i-1,l/2,R,C-l/2);
        }
    }else{
        if(C==l){
            return tmp[i]=rcnt(r-l/2,i-1,l/2,R,l/2)*2;
        }else if(C<=l/2){
            return rcnt(r-l/2,i-1,l/2,R,C);
        }else{
            return rcnt(r-l/2,i-1,l/2,R,l/2)+rcnt(r-l/2,i-1,l/2,R,C-l/2);
        }
    }
}
long long lcnt(long long r,long long i,long long l,long long R,long long C){
    if(C==0)return 0;
    if(l==1)return 1;
    if(tmp[i]!=0 && l==C)return tmp[i];
    if(R>r-l/2){
        if(C==l)return tmp[i]=lcnt(r,i-1,l/2,R,min(C,l/2));
        return lcnt(r,i-1,l/2,R,min(C,l/2));
    }else{
        if(C==l){
            return tmp[i]=lcnt(r-l/2,i-1,l/2,R,l/2)*2;
        }else if(C<=l/2){
            return lcnt(r-l/2,i-1,l/2,R,C);
        }else{
            return lcnt(r-l/2,i-1,l/2,R,l/2)+lcnt(r-l/2,i-1,l/2,R,C-l/2);
        }
    }
}
long long solve(long long r,long long c,long long w){
    long long i=0,l=1;
    while(l<r || l<c+w-1){
        l*=2;
        i++;
    } 
    memset(tmp,0,sizeof(tmp));
    long long L=lcnt(l,i,l,r,c-1);
    memset(tmp,0,sizeof(tmp));
    long long R=rcnt(l,i,l,r,l-c-w+1);
    memset(tmp,0,sizeof(tmp));
    long long all=lcnt(l,i,l,r,l);
    long long C=cnt(l,i,l,r);
    long long mid=all-L-R;
    if(L%C!=0)mid+=(L%C);
    return mid%C==0?mid/C:mid/C+1;
}
int main(){
    int q;
    scanf("%d",&q);
    while(q--){
        long long a,b,w,h;
        scanf("%lld %lld %lld %lld",&a,&b,&w,&h);
        a++;
        b++;
        long long res=0;
        res+=solve(b,a,w);
        res+=solve(a,b,h);
        res-=solve(a,b,1);
        printf("%lldn",res);
    }
    return 0;
}
View Code    

相关内容推荐