啊今天有点挂机啊

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

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

然后我疯狂优化暴力

然后去世了

最后半小时F也没写出来

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

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

这肯定是完蛋了啊

A:签到

#include 
      
       #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();}
      

B:签到

#include
      
       #include
       
        #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;}
       
      

C:交互题 贪心的贴墙走 

#include
      
       #include
       
        #include
        
         using namespace std;int x, y;int dx[] = {
    1, 0, -1, 0};int dy[] = {
    0, 1, 0, -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;}
        
       
      

D:

一开始想的暴力是我暴力分解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 
      
       #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
       
         tmp;map
        
          > 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
         
           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();}
         
        
       
      

E:签到题

#include
      
       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;}
      

F:

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

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

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

然后就没了

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

然后就乱了

比较简洁的做法也有很多

 可以先走到角上 然后bfs2步

#include
      
       #define ll long longusing namespace std;ll T,ax,ay,aw,ah,bx,by,bw,bh,ans,k;ll xx[4]={
    0,0,1,-1};ll yy[4]={
    1,-1,0,0};struct node{    ll x,y,s;    node(ll xx,ll yy,ll ss){        x=xx;y=yy;s=ss;    }};queue
       
        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,y,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,ss(ax+dx*aw,ay-dy*ah));        ans=max(ans,ss(ax-dx*aw,ay-dy*ah));        printf("%lld\n",ans);    }    return 0;}
       
      

 

G:数位DP

#include
      
        #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<
      

H:二分+几何

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

二分

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

#include
      
        #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
       
        
         0)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 的交点    return dcmp(Cross(k3-k1,k4-k1)-Cross(k3-k2,k4-k2))!=0;}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){    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 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))!=1&&    dcmp(Cross(q2-q1,p1-q1)*Cross(q2-q1,p2-q1))!=1;}bool isSS_s(Point p1,Point p2,Point q1,Point q2){    return dcmp(Cross(p2-p1,q1-p1)*Cross(p2-p1,q2-p1))==-1    &&dcmp(Cross(q2-q1,p1-q1)*Cross(q2-q1,p2-q1))==-1;}db Area(vector
         
           A){ // 多边形用 vector
          
            表示 , 逆时针  求面积     db ans=0;    for (int i=0;i
           
            0&&dcmp(Length(ins-p[pl])-k)<=0;}bool Check(int pl,int pr,int b,int k){ int a=(b-1+n)%n; Point ins=getLL(p[a],p[b],p[pl],p[pr]); return dcmp(Length(ins-p[pl])-k)==0;}int main(){ scanf("%d%d",&n,&Q); for(int i=0;i
           
          
         
        
       
      

L:矩阵优化最短路dp

#include 
      
       #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
       
         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, v, 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;    }}
       
      

 J:

对于每个询问建立虚树

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
       
        #define maxn 300010#define ll long long#define lc k<<1#define rc k<<1|1#define mid (l+r)/2using 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][2],dis[maxn],S[maxn*4],laz[maxn*4];struct node{    int v,t,pre;}e[maxn*2];vector
        
         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+1)*laz[k];    S[rc]+=(r-mid)*laz[k];    laz[lc]+=laz[k];laz[rc]+=laz[k];    laz[k]=0;}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+1,r);    }}void Insert(int k,int l,int r,int x,int y,ll z){    if(x<=l&&y>=r){        S[k]+=(r-l+1)*z;laz[k]+=z;        return;    }    if(laz[k])Up(k,l,r);    if(x<=mid)Insert(lc,l,mid,x,y,z);    if(y>mid)Insert(rc,mid+1,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);    else return Query(rc,mid+1,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]=1;son[now]=0;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+1,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;    if(son[now]==0)return;    dfs(son[now],fatr);    for(int i=head[now];i;i=e[i].pre){        int v=e[i].v;if(fat[v]==0)dfs(v,v);    }}int cmp1(const P &x,const P &y){    return lef[x.oo]
         
          1&&lef[s[top-1]]>=lef[lca]){        G[s[top-1]].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][0]=0;    for(int i=0;i
          
           c[v])Insert(1,1,n,lef[u],rig[u],w);            else Insert(1,1,n,lef[v],rig[v],w);        }        else {            scanf("%d",&k);top=0;            for(int i=1;i<=k;i++){                scanf("%d",&a[i].oo);a[i].o=i;            }             sort(a+1,a+1+k,cmp1);            for(int i=1;i<=k;i++)Add(a[i].oo);            while(top>1){                G[s[top-1]].push_back(s[top]);top--;            }            sort(a+1,a+1+k,cmp2);            DP1(s[1]);DP2(s[1],0);            for(int i=1;i<=k;i++)                printf("%lld ",max(dp[a[i].oo][0],dp[a[i].oo][1]));            printf("\n");        }            }    return 0;}/*51 2 22 3 22 4 21 5 1322 2 414 2 522 2 4*/