SDU暑假排位第一场 (Gym - 100889)_C

概述啊今天有点挂机啊 D题和队友暴力后发现一组数据跑得飞快然后遇上1e5组数据就没了..... 然后我疯狂优化暴力然后去世了最后半小时F也没写出来主要还是最后有点慌并且没有考虑清楚导致情况越写越多最后写了23个if 这肯定是完蛋了啊 A:签到 #include <bits/stdc++.h>#define int long longtypedef long long ll;u

啊今天有点挂机啊

D题和队友暴力后发现一组数据跑得飞快

然后遇上1e5组数据就没了.....

然后我疯狂优化暴力

然后去世了

最后半小时F也没写出来

主要还是最后有点慌并且没有考虑清楚

导致情况越写越多最后写了23个if

这肯定是完蛋了啊

A:签到

#include <bits/stdc++.h>#define int long longtypedef long long ll;using namespace std;const int N = 2e5 + 10;int n,a[N];voID ss() {    cin >> n;    for (int i = 1; i <= n; i++)cin >> a[i];    sort(a + 1,a + 1 + n);    int ans = 0;    for (int i = 1; i <= n / 2; i++) ans += a[n - i + 1] - a[i];    cout << ans << endl;}int32_t main() {    ios::sync_with_stdio(0),cin.tIE(0);    int T;    cin >> T;    while (T--)ss();}

VIEw Code

B:签到

#include<iostream>#include<cstdio>#define MAXN 100005#define ll long longusing namespace std;int n;ll a[MAXN];int solve(){    int l = 1,r = n,cnt = 0;    ll lsum = 0,rsum = 0;    if (n == 1) return 0;    while (l <= r) {        if (lsum < rsum) {            ++cnt;            lsum += a[L++];        }        else if (lsum > rsum) {            ++cnt;            rsum += a[r--];        }        else {            lsum = a[L++];            rsum = a[r--];        }    }    if (lsum != rsum) ++ cnt;    return cnt;}voID input(){    int T;    scanf("%d",&T);        while (T--){        scanf("%d",&n);        for (int i = 1; i <= n;++i){            scanf("%d",&a[i]);        }        int ans = solve();        printf("%d\n",ans);    }}int main(){    input();    return 0;}

VIEw Code

C:交互题贪心的贴墙走

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int x,y;int dx[] = {1,0,-1,0};int dy[] = {0,1,-1};char iin[60];char* str[] = {"DOWN","RIGHT","UP","left"};bool judge(int nx,int ny,int dir){    if (!x || !y) {        return 0;    }    cout << "LOOK " << str[dir] << endl;    cin >> iin;    return !strcmp(iin,"SAFE");}voID input(){    int dir = 1;    x = y = 1;    while (true) {        dir = (dir+3) % 4;        while (!judge(x+dx[dir],y+dy[dir],dir)) {            dir = (dir+1) % 4;        }        x += dx[dir];        y += dy[dir];        cout << "GO " << str[dir] << endl;        cin >> iin;        if (!strcmp(iin,"YES")) {            break;        }    }}int main(){    input();    return 0;}

VIEw Code

一开始想的暴力是我暴力分解N 把它分解成一些数的乘积

那么这些数可以作为某个ans的质因数指数

在选取质因子再去重复

然后t的死死的

在这个思路上挣扎了1小时之后投了扔给队友

幸好最后一小时队友找到了简单解法

对于一个ans 把他分解为p1^a1*p2^a2*...*pm^am

那么有(a1+1)(a2+1)*...*(am+1)==n

对n分解为p1^b1*p2^b2*...*pk^bk

对于b1个p1 把他分配到m个括号中

设第i个括号分了ci 有 c1+c2+...+cm=b1

简单的组合数问题

同理 p2 pk也是最后乘起来

这样就很巧妙的避免了重复

因为就算某两个括号的值相同

但是他们是作为两个不同的素数的指数

ans之间一定不同故不重复

#include <bits/stdc++.h>#define int long long#pragma GCC optimize(3)#define endl "\n"typedef long long ll;using namespace std;ll mod = 1e9 + 7;int n,m;vector<int> tmp;map<int,map<int,int> > PP;int f[100000];int f1[110];ll ans;ll qpow(ll a,ll n) {    ll ans = 1;    for (; n; n >>= 1,a = a * a % mod) if (n & 1) ans = ans * a % mod;    return ans;}vector<int> c;voID get(int n) {    for (int i = 2; i * i <= n; i++) {        if (n % i == 0) {            int cnt = 0;            while (n % i == 0)n /= i,cnt++;            c.push_back(cnt);        }    }    if (n > 1)c.push_back(1);}int C(int n,int m) {    if (m > n)return 0;    int res = 1;    for (int i = n; i >= n - m + 1; i--) {        res = (res * i) % mod;    }    return res * f1[m] % mod;}voID ss() {    cin >> n >> m;    c.clear();    int ans = 1;    get(n);    for (auto p:c) {        ans = (ans * C(m + p - 1,p)) % mod;    }    cout << ans << endl;}int32_t main() {    ios::sync_with_stdio(0),cin.tIE(0);    f1[0] = 1;    for (int i = 1; i <= 100; i++) f1[i] = 1LL * f1[i - 1] * i % mod;    for (int i = 1; i <= 100; i++) f1[i] = qpow(f1[i],mod - 2);    int T;    cin >> T;    while (T--)ss();}

VIEw Code

E:签到题

#include<cstdio>using namespace std;int T,n,m;int main(){    scanf("%d",&T);    while(T--){        int u,v,falg=0;        scanf("%d%d",&n,&m);        for(int i=1;i<=m;i++){            scanf("%d%d",&u,&v);            if(u==1&&v==n)falg=1;        }        if(falg)printf("Jorah Mormont\n");        else printf("Khal Drogo\n");    }    return 0;}

VIEw Code

一开始的思路是,按A矩阵的长宽离散坐标系并把A平移到原点

然后考虑A平移后和B相交的情况

四个角四个角附近的8个格子 B过坐标轴的四个各自四个角向内部走一个的四个格子.....

然后就没了

这题就属于没想好就开始摸键盘一开始大体想的情况很少然后写的过程中打补丁

然后就乱了

比较简洁的做法也有很多

可以先走到角上然后bfs2步

#include<bits/stdc++.h>#define ll long longusing namespace std;ll T,ax,ay,aw,ah,bx,by,bw,bh,ans,k;ll xx[4]={0,-1};ll yy[4]={1,0};struct node{    ll x,y,s;    node(ll xx,ll yy,ll ss){        x=xx;y=yy;s=ss;    }};queue<node>q;ll Cal(ll x,ll y){    ll dx=max(0ll,min(x+aw,bx+bw)-max(x,bx));    ll dy=max(0ll,min(y+ah,by+bh)-max(y,by));    return dx*dy;}ll ss(ll x,ll y){    ll res=0,lim=min(2ll,k);    q.push(node(x,0));    while(!q.empty()){        node Now=q.front();q.pop();        res=max(res,Cal(Now.x,Now.y));        if(Now.s==lim)continue;        for(ll i=0;i<4;i++){            ll nx=Now.x+xx[i]*aw;            ll ny=Now.y+yy[i]*ah;            q.push(node(nx,ny,Now.s+1));        }    }    return res;}int main(){    scanf("%lld",&T);    while(T--){        scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld",&ax,&ay,&aw,&ah,&bx,&by,&bw,&bh,&k);        ll dx,dy;ans=0;        if(bx>=ax+aw)dx=(bx-ax)/aw;        else if(bx+bw<=ax)dx=(ax-bx-bw)/aw+1;        else dx=0;        if(by>=ay+ah)dy=(by-ay)/ah;        else if(by+bh<=ay)dy=(ay-by-bh)/ah+1;        else dy=0;        k-=dx+dy;        if(k<0){            printf("0\n");continue;        }        ans=max(ans,ss(ax+dx*aw,ay+dy*ah));        ans=max(ans,ss(ax-dx*aw,ay-dy*ah));        ans=max(ans,ay-dy*ah));        printf("%lld\n",ans);    }    return 0;}

VIEw Code

G:数位DP

#include<bits/stdc++.h> #define ll long longusing namespace std;ll T,L,R,A,B,f[100][2][2][2][2];ll Dfs(ll Now,ll okx1,ll okx2,ll oky,ll okz){    if(Now<0)return 0;    if(f[Now][okx1][okx2][oky][okz]!=-1)return f[Now][okx1][okx2][oky][okz];    ll xl=0,xr=1,yl=0,yr=1,zl=0,zr=1;    if(okx1)xl=(L>>Now)&1;    if(okx2)xr=(R>>Now)&1;    if(oky)yr=(A>>Now)&1;    if(okz)zr=(B>>Now)&1;    ll res=0;    for(ll i=xl;i<=xr;i++)        for(ll j=yl;j<=yr;j++)            for(ll k=zl;k<=zr;k++){                ll tis=((i^j)+(j&k)+(k^i))*(1ll<<Now);                res=max(res,tis+Dfs(Now-1,okx1&&i==xl,okx2&&i==xr,oky&&j==yr,okz&&k==zr));            }    return f[Now][okx1][okx2][oky][okz]=res;}int main(){    scanf("%lld",&T);    while(T--){        memset(f,-1,sizeof(f));        scanf("%lld%lld%lld%lld",&L,&R,&A,&B);        printf("%lld\n",Dfs(62,1));    }    return 0;}

VIEw Code

H:二分+几何

平移到原点之后在能和x正半轴产生交点的边中交点横坐标和距离原点的距离(凸包上逆时针距离几个点)是有单调性的

二分

最后其实不用平移旋转每个点只需要把x=k这个线挪动就好了

#include<bits/stdc++.h> #define db double#define Vector Point#define maxn 100010using namespace std;struct Point{    db x,y;    Point(db X=0,db Y=0){x=X;y=Y;}};Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}Vector operator * (Vector A,db p){return Vector(A.x*p,A.y*p);}Vector operator / (Vector A,db p){return Vector(A.x/p,A.y/p);}bool operator < (const Point &a,const Point &b){    return a.x<b.x||(a.x==b.x&&a.y<b.y);}const db eps=1e-10;int dcmp(db x){    if(fabs(x)<eps)return 0;    else return x<0?-1:1;}bool operator ==(const Point &a,const Point &b){    return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}db Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//A B 点积db Length(Vector A){return sqrt(Dot(A,A));}//向量长度db Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}//A B 夹角db Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//A B 叉积db Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}//A B 构成的平行四边形面积2倍Vector Rotate(Vector A,db rad){//A逆时针旋转rad    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}Vector normal(Vector A){//返回A的单位法向量    return Vector(-A.y/Length(A),A.x/Length(A));}//点和直线Point GetlineIntersection(Point P,Vector v,Point Q,Vector w){//返回直线P+tv Q+tw的交点    Vector u=P-Q;    db t=Cross(w,u)/Cross(v,w);    return P+v*t;}db distancetoline(Point P,Point A,Point B){//P到直线AB的距离    Vector v1=B-A,v2=P-A;    return fabs(Cross(v1,v2)/Length(v1));}db distancetoSegment(Point P,Point B){//P到线段AB的距离    if(A==B)return Length(P-A);    Vector v1=B-A,v2=P-A,v3=P-B;    if(dcmp(Dot(v1,v2))<0)return Length(v2);    else if(dcmp(Dot(v1,v3))>0)return Length(v3);    else return fabs(Cross(v1,v2))/Length(v1);}Point GetlineProjection(Point P,Point B){//P在直线AB上的投影    Vector v=B-A;    return A+v*(Dot(v,P-A)/Dot(v,v));}//bool isSL(Point p1,Point p2,Point q1,Point q2){//判断直线p1p2和线段q1q2有无交点(不严格)//     return dcmp(Cross(p2-p1,q1-p1)*Cross(p2-p1,q2-p1))!=1;//}//bool isSL_s(Point p1,Point q2){//判断直线p1p2和线段q1q2有无交点(严格)//     return dcmp(Cross(p2-p1,q2-p1))==-1;//}int isll(Point k1,Point k2,Point k3,Point k4){// 求直线 k1,k2 和 k3,k4 的交点    return dcmp(Cross(k3-k1,k4-k1)-Cross(k3-k2,k4-k2))!=0;}Point getLL(Point k1,Point k4){    db w1=Cross(k1-k3,k4-k3),w2=Cross(k4-k3,k2-k3); return (k1*w2+k2*w1)/(w1+w2);}bool intersect(db l1,db r1,db l2,db r2){    if(dcmp(l1-r1)==1)swap(l1,r1);if(dcmp(l2-r2)==1)swap(l2,r2);    return !(dcmp(r1-l2)==-1||dcmp(r2-l1)==-1);}bool isSS(Point p1,Point q2){    return intersect(p1.x,p2.x,q1.x,q2.x)&&intersect(p1.y,p2.y,q1.y,q2.y)&&    dcmp(Cross(p2-p1,q2-p1))!=1&&    dcmp(Cross(q2-q1,p1-q1)*Cross(q2-q1,p2-q1))!=1;}bool isSS_s(Point p1,Point q2){    return dcmp(Cross(p2-p1,q2-p1))==-1    &&dcmp(Cross(q2-q1,p2-q1))==-1;}db Area(vector<Point> A){ // 多边形用 vector<point> 表示,逆时针  求面积     db ans=0;    for (int i=0;i<A.size();i++) ans+=Cross(A[i],A[(i+1)%A.size()]);    return ans/2;}int n,Q;Point p[maxn];bool Judge(int pl,int pr,int dis,int k){    int a=(pr+dis)%n;    int b=(a+1)%n;    Point ins=getLL(p[a],p[b],p[pl],p[pr]);    return dcmp(Length(ins-p[pl])-Length(ins-p[pr]))>0&&dcmp(Length(ins-p[pl])-k)<=0;}bool Check(int pl,int b,int k){    int a=(b-1+n)%n;    Point ins=getLL(p[a],p[pr]);    return dcmp(Length(ins-p[pl])-k)==0;}int main(){    scanf("%d%d",&Q);    for(int i=0;i<n;i++){        scanf("%lf%lf",&p[i].x,&p[i].y);    }    int pl,pr,k,ans=-1;    while(Q--){        scanf("%d%d",&pl,&k);pr=(pl+1)%n;        int l=0,r=n-1;        while(l<=r){            int mID=(l+r)/2;            if(Judge(pl,mID,k)){                ans=(pr+mID+1)%n;l=mID+1;            }            else r=mID-1;        }        if(Check(pl,k))printf("%d %d\n",(ans-1+n)%n,ans);        else printf("%d\n",ans);    }    return 0;} /*7 35 52 60 5-1 30 06 06 34 74 84 100007 35 42 50 4-1 20 06 06 24 74 84 10000*/

VIEw Code

L:矩阵优化最短路dp

#include <bits/stdc++.h>#define int long longtypedef long long ll;using namespace std;const int MT = 200;int n,m,k;ll mod = 1e9 + 7;ll inf = 3e18;struct Matrix {    pair<int,int> v[MT][MT];    voID init() {        for (int i = 1; i <= n; i++)            for (int j = 1; j <= n; j++)                v[i][j] = {inf,0};    }    Matrix operator*(const Matrix B) const {        Matrix C;        C.init();        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= n; j++) {                for (int k = 1; k <= n; k++) {                    if (v[i][k].first + B.v[k][j].first < C.v[i][j].first) {                        C.v[i][j].first = v[i][k].first + B.v[k][j].first;                    }                }                for (int k = 1; k <= n; k++) {                    if (v[i][k].first + B.v[k][j].first == C.v[i][j].first) {                        (C.v[i][j].second += v[i][k].second * B.v[k][j].second) %= mod;                    }                }            }        }        return C;    }} mp;int32_t main() {    ios::sync_with_stdio(0),cin.tIE(0);    cin >> n >> m >> k;    mp.init();    while (m--) {        int u,w;        cin >> u >> v >> w;        mp.v[u][v] = {w,1};        mp.v[v][u] = {w,1};    }    Matrix ans = mp;    k--;    for (; k; k >>= 1,mp = mp * mp) if (k & 1) ans = ans * mp;    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= n; j++) {            if (ans.v[i][j].first >= inf)cout << "X 0 ";            else                cout << ans.v[i][j].first << " " << ans.v[i][j].second << " ";        }        cout << endl;    }}