SDU暑假排位第一场 (Gym

啊今天有点挂机啊

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

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

然后我疯狂优化暴力

然后去世了

最后半小时F也没写出来

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

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

这肯定是完蛋了啊

A:签到

#include <bits/stdc++.h>

#define int long long
typedef long long ll;
using namespace std;
;
int n, a[N];

void ss() {
    cin >> n;
    ; i <= n; i++)cin >> a[i];
    sort(a + , a +  + n);
    ;
    ; i <= n / ; i++) ans += a[n - i + ] - a[i];
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(), cin.tie();
    int T;
    cin >> T;
    while (T--)ss();
}

B:签到

#include<iostream>
#include<cstdio>
#define MAXN 100005
#define ll long long
using namespace std;
int n;
ll a[MAXN];

int solve(){
    , r = n, cnt = ;
    ll lsum = , rsum = ;
    ) ;

    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);
        ; i <= n;++i){
            scanf("%d", &a[i]);
        }
        int ans = solve();
        printf("%d\n", ans);
    }
}

int main(){
    input();
    ;
}

C:交互题贪心的贴墙走

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int x, y;
, , -, };
, , , -};

];
char* str[] = {"DOWN", "RIGHT", "UP", "LEFT"};

bool judge(int nx, int ny, int dir){
    if (!x || !y) {
        ;
    }
    cout << "LOOK " << str[dir] << endl;
    cin >> iin;
    return !strcmp(iin, "SAFE");
}

void input(){
    ;
    x = y = ;
    while (true) {
        dir = (dir+) % ;
        while (!judge(x+dx[dir], y+dy[dir], dir)) {
            dir = (dir+) % ;
        }
        x += dx[dir];
        y += dy[dir];
        cout << "GO " << str[dir] << endl;
        cin >> iin;
        if (!strcmp(iin, "YES")) {
            break;
        }
    }
}

int main(){
    input();
    ;
}

一开始想的暴力是我暴力分解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 + ;

int n, m;

vector<int> tmp;
map<int, map<int, int> > PP;
];
];
ll ans;

ll qpow(ll a, ll n) {
    ll ans = ;
    , a = a * a % mod) ) ans = ans * a % mod;
    return ans;
}

vector<int> c;

void get(int n) {
    ; i * i <= n; i++) {
        ) {
            ;
            )n /= i, cnt++;
            c.push_back(cnt);
        }
    }
    )c.push_back();
}

int C(int n, int m) {
    ;
    ;
    ; i--) {
        res = (res * i) % mod;
    }
    return res * f1[m] % mod;
}

void ss() {
    cin >> n >> m;
    c.clear();
    ;
    get(n);
    for (auto p:c) {
        ans = (ans * C(m + p - , p)) % mod;
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(), cin.tie();
    f1[] = ;
    ; i <= ; i++) f1[i] = 1LL * f1[i - ] * i % mod;
    ; i <= ; i++) f1[i] = qpow(f1[i], mod - );
    int T;
    cin >> T;
    while (T--)ss();
}

E:签到题

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

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

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

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

然后就没了

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

然后就乱了

比较简洁的做法也有很多

可以先走到角上然后bfs2步

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,ax,ay,aw,ah,bx,by,bw,bh,ans,k;
ll xx[]={,,,-};
ll yy[]={,-,,};
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=,lim=min(2ll,k);
    q.push(node(x,y,));
    while(!q.empty()){
        node now=q.front();q.pop();
        res=max(res,Cal(now.x,now.y));
        if(now.s==lim)continue;
        ;i<;i++){
            ll nx=now.x+xx[i]*aw;
            ll ny=now.y+yy[i]*ah;
            q.push(node(nx,ny,now.s+));
        }
    }
    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=;
        if(bx>=ax+aw)dx=(bx-ax)/aw;
        ;
        ;
        if(by>=ay+ah)dy=(by-ay)/ah;
        ;
        ;
        k-=dx+dy;
        ){
            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,ss(ax+dx*aw,ay-dy*ah));
        ans=max(ans,ss(ax-dx*aw,ay-dy*ah));
        printf("%lld\n",ans);
    }
    ;
}

G:数位DP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,L,R,A,B,f[][][][][];
ll Dfs(ll now,ll okx1,ll okx2,ll oky,ll okz){
    );
    )return f[now][okx1][okx2][oky][okz];
    ll xl=,xr=,yl=,yr=,zl=,zr=;
    ;
    ;
    ;
    ;
    ll res=;
    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-,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,-,sizeof(f));
        scanf("%lld%lld%lld%lld",&L,&R,&A,&B);
        printf(,,,,));
    }
    ;
}

H:二分+几何

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

二分

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

#include<bits/stdc++.h>
#define db double
#define Vector Point
#define maxn 100010
using namespace std;
struct Point{
    db x,y;
    Point(db X=,db Y=){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);
}
;
int dcmp(db x){
    ;
    ?-:;
}
bool operator ==(const Point &a,const Point &b){
    &&dcmp(a.y-b.y)==;
}
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 A,Point B){//P到线段AB的距离
    if(A==B)return Length(P-A);
    Vector v1=B-A,v2=P-A,v3=P-B;
    )return Length(v2);
    )return Length(v3);
    else return fabs(Cross(v1,v2))/Length(v1);
}
Point GetLineProjection(Point P,Point A,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 p2,Point q1,Point q2){//判断直线p1p2和线段q1q2有无交点(严格)
//     return dcmp(Cross(p2-p1,q1-p1)*Cross(p2-p1,q2-p1))==-1;
//}
int isLL(Point k1,Point k2,Point k3,Point k4){// 求直线 k1,k2 和 k3,k4 的交点
    ;
}
Point getLL(Point k1,Point k2,Point k3,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){
    )swap(l1,r1);)swap(l2,r2);
    ||dcmp(r2-l1)==-);
}
bool isSS(Point p1,Point p2,Point q1,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,q1-p1)*Cross(p2-p1,q2-p1))!=&&
    dcmp(Cross(q2-q1,p1-q1)*Cross(q2-q1,p2-q1))!=;
}
bool isSS_s(Point p1,Point p2,Point q1,Point q2){

    &&dcmp(Cross(q2-q1,p1-q1)*Cross(q2-q1,p2-q1))==-;
}
db Area(vector<Point> A){ // 多边形用 vector<point> 表示 , 逆时针  求面积
    db ans=;
    ;i<A.size();i++) ans+=Cross(A[i],A[(i+)%A.size()]);
    ;
}
int n,Q;
Point p[maxn];
bool Judge(int pl,int pr,int dis,int k){
    int a=(pr+dis)%n;
    )%n;
    Point ins=getLL(p[a],p[b],p[pl],p[pr]);
    &&dcmp(Length(ins-p[pl])-k)<=;
}
bool Check(int pl,int pr,int b,int k){
    +n)%n;
    Point ins=getLL(p[a],p[b],p[pl],p[pr]);
    ;
}
int main(){
    scanf("%d%d",&n,&Q);
    ;i<n;i++){
        scanf("%lf%lf",&p[i].x,&p[i].y);
    }
    ;
    while(Q--){
        scanf()%n;
        ,r=n-;
        while(l<=r){
            ;
            if(Judge(pl,pr,mid,k)){
                ans=(pr+mid+)%n;l=mid+;
            }
            ;
        }
        +n)%n,ans);
        else printf("%d\n",ans);
    }
    ;
}
/*
7 3
5 5
2 6
0 5
-1 3
0 0
6 0
6 3
4 7
4 8
4 10000

7 3
5 4
2 5
0 4
-1 2
0 0
6 0
6 2
4 7
4 8
4 10000
*/

L:矩阵优化最短路dp

#include <bits/stdc++.h>

#define int long long
typedef long long ll;
using namespace std;

;

int n, m, k;

ll mod = 1e9 + ;
ll inf = 3e18;

struct Matrix {
    pair<int, int> v[MT][MT];

    void init() {
        ; i <= n; i++)
            ; j <= n; j++)
                v[i][j] = {inf, };
    }

    Matrix operator*(const Matrix B) const {
        Matrix C;
        C.init();
        ; i <= n; i++) {
            ; j <= n; j++) {
                ; 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;
                    }
                }
                ; 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(), cin.tie();
    cin >> n >> m >> k;
    mp.init();
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        mp.v[u][v] = {w, };
        mp.v[v][u] = {w, };
    }
    Matrix ans = mp;
    k--;
    , mp = mp * mp) ) ans = ans * mp;
    ; i <= n; i++) {
        ; 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;
    }
}

对于每个询问建立虚树
dp[i][0] 便是在虚树中i向下走的最远距离
dp[i][1] 便是在虚树中i向上走的最远距离
O(k)的dp
关键是怎么拿到虚树的边权
其实具体的记下每个边权
我们可以慢一点在原图中查
反正节点的相对关系是不变的

原图按dfs序建立线段树维护i到根节点的距离
每次修改(u,v)就修改v的子树
虚树中dp的时候
dis(u,v)=Query(u)+Query(v)-2*Query(lca(u,v))
dp[i][0]=max(dp[v][0]+dis(u,v))
dp[i][1]=max(dp[fa][1],dp[fa][0])+dis(u,v)

/*

*/
#include<bits/stdc++.h>
#define maxn 300010
#define ll long long
#define lc k<<1
#define rc k<<1|1
#define mid (l+r)/2
using namespace std;
int n,Q,num,head[maxn],fa[maxn],fat[maxn],c[maxn],lef[maxn],rig[maxn],tot,A[maxn],s[maxn],top;
int siz[maxn],son[maxn],RR[maxn];
ll dp[maxn][],dis[maxn],S[maxn*],laz[maxn*];
struct node{
    int v,t,pre;
}e[maxn*];
vector<int>G[maxn];
struct P{
    int o,oo;
}a[maxn];
void Add(int from,int to,int dis){
    num++;e[num].v=to;
    e[num].t=dis;
    e[num].pre=head[from];
    head[from]=num;
}
void Up(int k,int l,int r){
    S[lc]+=(mid-l+)*laz[k];
    S[rc]+=(r-mid)*laz[k];
    laz[lc]+=laz[k];laz[rc]+=laz[k];
    laz[k]=;
}
void Build(int k,int l,int r){
    if(l==r){
        S[k]=dis[RR[l]];return;
    }
    else {
        Build(lc,l,mid);Build(rc,mid+,r);
    }
}
void Insert(int k,int l,int r,int x,int y,ll z){
    if(x<=l&&y>=r){
        S[k]+=(r-l+)*z;laz[k]+=z;
        return;
    }
    if(laz[k])Up(k,l,r);
    if(x<=mid)Insert(lc,l,mid,x,y,z);
    ,r,x,y,z);
    S[k]=S[lc]+S[rc];
}
ll Query(int k,int l,int r,int x){
    if(l==r)return S[k];
    if(laz[k])Up(k,l,r);
    if(x<=mid)return Query(lc,l,mid,x);
    ,r,x);
}
void Dfs(int now,int from,int dep,ll cos){
    lef[now]=++tot;RR[tot]=now;fa[now]=from;c[now]=dep;
    siz[now]=;son[now]=;dis[now]=cos;
    for(int i=head[now];i;i=e[i].pre){
        int v=e[i].v;if(v==from)continue;
        Dfs(v,now,dep+,cos+e[i].t);
        siz[now]+=siz[v];
        if(siz[v]>siz[son[now]])son[now]=v;
    }
    rig[now]=tot;
}
void dfs(int now,int fatr){
    fat[now]=fatr;
    )return;
    dfs(son[now],fatr);
    for(int i=head[now];i;i=e[i].pre){
        )dfs(v,v);
    }
}
int cmp1(const P &x,const P &y){
    return lef[x.oo]<lef[y.oo];
}
int cmp2(const P &x,const P &y){
    return x.o<y.o;
}
int LCA(int x, int y) {
    while(fat[x]!=fat[y]){
        if(c[fat[x]]<c[fat[y]])swap(x,y);
        x=fa[fat[x]];
    }
    if(c[x]<c[y])swap(x,y);
    return y;
}
void Add(int p){
    ){
        s[++top]=p;return;
    }
    int lca=LCA(p,s[top]);
    if(lca==s[top]){
        s[++top]=p;return;
    }
    &&lef[s[top-]]>=lef[lca]){
        G[s[top-]].push_back(s[top]);top--;
    }
    if(lca!=s[top]){
        G[lca].push_back(s[top]);s[top]=lca;
    }
    s[++top]=p;
}
void DP1(int now){
    dp[now][]=;
    ;i<G[now].size();i++){
        int v=G[now][i];DP1(G[now][i]);
        ll di=Query(,,n,lef[v])-Query(,,n,lef[now]);
        dp[now][]=max(dp[now][],dp[v][]+di);
    }
}
void DP2(int now,int fa){
    dp[now][]=;
    ){
        ll di=Query(,,n,lef[now])-Query(,,n,lef[fa]);
        dp[now][]=dp[fa][]+di;
        ;i<G[fa].size();i++){
            int v=G[fa][i];
            ll dii=Query(,,n,lef[v])-Query(,,n,lef[fa]);
            ]=max(dp[now][],dp[v][]+di+dii);
        }
    }
    ;i<G[now].size();i++){
        int v=G[now][i];DP2(v,now);
    }
    G[now].clear();
}
int main(){
    scanf("%d",&n);int u,v,w;
    ;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        Add(u,v,w);Add(v,u,w);
    }
    Dfs(,,,);dfs(,);Build(,,n);
    int k,x;
    scanf("%d",&Q);while(Q--){
        scanf("%d",&x);
        ){
            scanf("%d%d%d",&u,&v,&w);
            for(int i=head[u];i;i=e[i].pre)
                if(e[i].v==v)w=w-e[i].t;
            ,,n,lef[u],rig[u],w);
            ,,n,lef[v],rig[v],w);
        }
        else {
            scanf(;
            ;i<=k;i++){
                scanf("%d",&a[i].oo);a[i].o=i;
            }
            sort(a+,a++k,cmp1);
            ;i<=k;i++)Add(a[i].oo);
            ){
                G[s[top-]].push_back(s[top]);top--;
            }
            sort(a+,a++k,cmp2);
            DP1(s[]);DP2(s[],);
            ;i<=k;i++)
                printf(],dp[a[i].oo][]));
            printf("\n");
        }

    }
    ;
}
/*
5
1 2 2
2 3 2
2 4 2
1 5 1
3
2
2 2 4
1
4 2 5
2
2 2 4
*/

巴特西

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

最新文章

热门文章