杭电杯第八场

个人题解，欢迎指正

P1001

思路：

奇数位和偶数为排序后交错输出即可

Code：

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}
const int N=1e5+5;
string s;
char c[2][N];
int d[2];

void ClearDewy(){
    cin>>s;d[1]=d[0]=0;
    for (int i = 0; i < s.size(); i++)
    {
        c[i&1][++d[i&1]]=s[i];
    }
    sort(c[0]+1,c[0]+d[0]+1);
    sort(c[1]+1,c[1]+d[1]+1);
    for (int i = 1; i <= d[1]; i++)
    {
        putchar(c[0][i]);putchar(c[1][i]);
    }
    if(d[0]>d[1])putchar(c[0][d[0]]);
    ptn;

}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    ClearDewy();
    return 0;
}

P1004

签到题

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x ;scanf("%lld",&x);return x;}
inline void writ(ll x){printf("%lld",x);}


int n;

void ClearDewy(){
    n=read();
    printf("%d\n",2*n);


}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    ClearDewy();
    return 0;
}

P1005

逐步向后处理，利用处理过的节点进行“跳跃”，得到由每个点出发的左右边界，最后判断即可

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0;scanf("%lld",&x);return x;};
inline void writ(ll x){printf("%lld",x);}

#define pii pair<int,int>


void ClearDewy(){
    int n=read(),m=read();
    vector<pii>a(n+2);
    vector<set<int>>pri(n+1);
    vector<int>e(n+1);
    e[0]=e[n]=1e9+7;a[n+1]={n+1,n+1};
    int x,y;
    for (int i = 1; i <= n; i++)
    {
        a[i]={i,i};
        x=read();
        for (int j = 2; j <= x/j; j++)
        {
            if(x%j)continue;
            pri[i].insert(j);
            while (!(x%j))x/=j;
        }
        if(x>1)pri[i].insert(x);
    }
    for (int i = 1; i < n; i++)
    {
        e[i]=read();
    }
    for (int i = 1; i <= n; i++)
    {
        int l=i-1,r;
        while (l&&pri[i].count(e[l]))
        {
            pri[i].insert(pri[l].begin(),pri[l].end());
            a[i].first=a[l].first;
            a[i].second=max(a[i].second,a[l].second);
            l=a[i].first-1;
        }
        r=a[i].second;
        while (pri[i].count(e[r]))
        {
            r++;
            pri[i].insert(pri[r].begin(),pri[r].end());
            a[i].second=r;
            while (l&&pri[i].count(e[l]))
            {
                pri[i].insert(pri[l].begin(),pri[l].end());
                a[i].first=a[l].first;
                a[i].second=max(a[i].second,a[l].second);
                l=a[i].first-1;
            }
            r=a[i].second;
        }
    }

    // for(int i = 1;i <= n;i++)
    //     cout << a[i].first << " " << a[i].second <<endl;
    while (m--)
    {
        x=read();y=read();
        if(y>=a[x].first&&y<=a[x].second)puts("Yes");
        else puts("No");
    }
    
}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    ClearDewy();
    return 0;
}

P1008

递归返回时当前度数大于一时删除该节点，最后遍历统计

Code：

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() { ll x = 0; scanf("%lld", &x); return x; };
inline void writ(ll x) { printf("%lld", x); }

void Qingtuan() {
    int n = read();
    vector<vector<int>>f(n+1);
    vector<bool>visi(n+1);
    vector<int>du(n+1);
    int x, y;
    for (int i = 1; i < n; i++)
    {
        x = read(); y = read();
        f[x].push_back(y); f[y].push_back(x);
        du[x]++; du[y]++;
    }

    function<int(int)>dfs=[&](int x)->int{
        int y=0;
        visi[x]=1;
        for(auto i:f[x]){
            if(!visi[i])y+=dfs(i);
        }
        if(y>1){
            du[x]=0;return 0;
        }
        return y+1;
    };

    dfs(1);
    int res=0;
    for (int i = 1; i <= n; i++)
    {
        if(du[i])res++;
    }
    printf("%d\n",res);
}



int main() {
    //cin.tie(nullptr)->sync_with_stdio(false);
    int size(512<<20);  // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    int T = read(); while (T--)
        Qingtuan();
    exit(0);
    return 0;
}

P1011

枚举宽可以分成的块数

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0;scanf("%lld",&x);return x;};
inline void writ(ll x){printf("%lld",x);}


int n,m,k;

void Qingtuan(){
    m=read();n=read();k=read();
    int res=0;
    int a,b;
    for (int i = 1; i <= m; i++)
    {
        a=m/i;
        if(!a)break;
        b=(k-1)/a+1;
        b=n/b;
        if(b<=0)continue;
        res=max(res,i+b-2);
    }
    printf("%d\n",res);

}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    Qingtuan();
    return 0;
}