一个晚上熬夜连续写两篇博客，好累啊。。

再次%%%丁思源霸霸AKdalao Siyuan

T1:

听说是普及组T1难度。。。因为没开longlong只有60分很伤

就是枚举到sqrt(n)暴力找质因子。。。

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,t;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&n);
        int flag=0;
        ll m=n;
        for(ll i=2;i<=sqrt(m);i++){
            while(n%i==0){
                printf("%lld ",i);
                n/=i;
                flag=1;
            }
        }
        if(n!=1) printf("%lld",n);
        puts("");
    }
    return 0;
}

T2:

又是一道大模拟。。。。

最近模拟越来越多了。。。

但是需要注意的是当n为奇数时最中间的一个数可能会变大。。。

再就是要加输出优化。。。

code:

#include<bits/stdc++.h>
using namespace std;
int n,a[1010][1010],x,cnt,tmp;
void print(int x){
    if(x<10) putchar(x+'0');
    else{
        print(x/10);
        putchar(x%10+'0');
    }
    return;
}
void solve(int now,int flag){
    if(flag==1){
        for(int i=now;i<=n-now+1;i++)a[now][i]=++cnt;
        for(int i=now+1;i<=n-now;i++)a[i][n-now+1]=++cnt;
        for(int i=n-now+1;i>=now;i--)a[n-now+1][i]=++cnt;
        for(int i=n-now;i>now;i--)a[i][now]=++cnt;
        tmp=cnt;
    }
    else{
        for(int i=now;i<=n-now+1;i++)a[i][now]=++cnt;
        for(int i=now+1;i<=n-now+1;i++)a[n-now+1][i]=++cnt;
        for(int i=n-now;i>=now;i--)a[i][n-now+1]=++cnt;
        for(int i=n-now;i>now;i--)a[now][i]=++cnt;
        tmp=cnt;
    }
    return ;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=(n+1)/2;i++){
        scanf("%d",&x);
        solve(i,x);        
    }
     if(n%2==1) a[(n+1)/2][(n+1)/2]=tmp-1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            print(a[i][j]),putchar(' ');
        puts("");
    }
    return 0;
}

T3:

多重背包模板。。。

首先讲讲二进制优化，就是把多重背包转换为01背包

当一个物品数量为s时，我们将它分解为2^0个,2^1……2^k个物品，最后还有s-1-2-4-……-2^k个物品

这样就可以保证若干个分解后的物品可以凑出1~s中的任意物品数量

别告诉我你不会01背包（反正我不会）

code:

#include<bits/stdc++.h>
using namespace std;
int n,v,w1,c1,m1;
int w[500010],c[500010],cnt;
int f[1000010];
int _pow(int x){
    if(!x) return 1;
    int cnt=1;
    for(int i=1;i<=x;i++)cnt*=2;
    return cnt;
}
void solve(int tot,int h,int va){
    int k=0;
    while(_pow(k)<=tot){
        tot-=_pow(k);
        w[++cnt]=h*_pow(k);
        c[cnt]=va*_pow(k);
        k++;
    }
    if(tot) w[++cnt]=tot*h,c[cnt]=tot*va;
    return;
}
int main(){
    scanf("%d%d",&n,&v);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&w1,&c1,&m1);
        solve(m1,w1,c1);
    }
    for(int i=1;i<=cnt;i++)
        for(int j=v;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("%d\n",f[v]);
    return 0;
}

T4:

状压DP，没有敲(std把我吓到了。。)

设f[i][j][s]表示到达i,j,钥匙的状态为s（即01串）能否做到

然后玄学转移。。。

T5：

首先想到一个只有20分的hash：

对于每一个皇后，枚举他的攻击路径，将坐标hash一下后去重，计算答案

但是这样的空间复杂度是n*m的，会爆炸

于是我们想到可以分成每一行来做。。。

接下来设h[i]表示目前这一行第i个格子是否被覆盖

然后可以初始化t，表示这一行没有被覆盖的格子数，初识t=m

分两种情况：

1.如果该格被某个皇后横向攻击的话，那么整行都会被覆盖，t=0

2.如果一格之前没有被攻击过，但是现在被攻击了，t--

最后对于每一行ans+=t

然后这里顺便打了个时间戳优化。。。

code:

#include<bits/stdc++.h>
using namespace std;
int hash[100010],n,m,k,ans,x[100010],y[100010];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=n;i++){
        int t=m;
        for(int j=1;j<=k;j++){
            if(x[j]==i){
                t=0;
                break;
            }
            if(hash[y[j]]!=i){
                hash[y[j]]=i;
                t--;
            }
            if((i+y[j]-x[j])>0&&(i+y[j]-x[j])<=m&&hash[i+y[j]-x[j]]!=i){
                hash[i+y[j]-x[j]]=i;
                t--;
            }
            if((y[j]+x[j]-i)>0&&(y[j]+x[j]-i)<=m&&hash[y[j]+x[j]-i]!=i){
                hash[y[j]+x[j]-i]=i;
                t--;
            }
        }    
        ans+=t;
    }
    printf("%d",ans);
    return 0;
}

T6:

要联通且边数最小那么肯定是一棵树。。

首先想到一个60分做法：

将边按边权sort一遍后，枚举最小边，使用并查集判断联通

一直往边权大的方向枚举，直到联通，更新答案，复杂度O(nm)

接下来是玄学标算，我也不知道为什么是对的。。

每次从上次计算完答案的区间起点开始，一直向上找联通块

找到之后从联通块中最大的边开始往下找联通块，不停地更新答案，复杂度O(n+m)（应该是的）

code:

#include<bits/stdc++.h>
#define se second
#define fi first
using namespace std;
int fa[100010],ans=1e9;
int n,m,a,b,c,l,r,cnt;
struct node{
    int x,y,z;
}edge[100010];
bool cmp(node x,node y){return x.z<y.z;}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
bool check(int now){
    int fx=getfa(edge[now].x),fy=getfa(edge[now].y);
    if(fx!=fy){
        cnt++;
        fa[fx]=fy;
        if(cnt==n-1){
            ans=min(ans,edge[r].z-edge[l].z);
            return true;
        }
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        edge[i]=(node){a,b,c};
    }
    sort(edge+1,edge+m+1,cmp);
    while(1){
        for(int j=1;j<=n;j++)fa[j]=j;
        cnt=0;
        while(r<m)if(check(++r)) break;
        if(cnt!=n-1) break;
        cnt=0;
        l=r+1;
        for(int j=1;j<=n;j++)fa[j]=j;
        while(l>1)if(check(--l)) break;
        if(cnt!=n-1) break;
        r=l;
    }
    if(ans==1e9) puts("-1");
    else printf("%d",ans);
    return 0;
}