Eternity

Until The End

随机100题(29/100)

发表于 更新于 分类于
本文字数： 58k 阅读时长 ≈ 52 分钟

“作为这一年的奋斗目标，难度：提高左右”

1.P4170 [CQOI2007]涂色

$date: 2022.4.10$

区间 $dp$ 模板题，转移方程有三种：

  1. $dp_{l,r}=1,l=r$
  2. $dp_{l,r}=\min\{dp_{l+1,r},dp_{l,r-1}\},op_l=op_r$
  3. $dp_{l,r}=\min\{dp_{l,r},dp_{l,k}+dp_{k+1,r}\},op_l \neq op_r,k \in [l,r]$

第一种，涂一块只需要一次即可；

而对于第二种，我们在涂的时候只需要再其子区间的时候多涂一块，不需要再涂一次，所以不用统计答案；

第三种，经典断点即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=51;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int dp[MAXN][MAXN],n,op[MAXN];
char str[MAXN];
inline int change(char s)
{
    return s-'A'+1;
}
int main()
{
    // freopen("dp-section.in","r",stdin);
    // freopen("dp-section.out","w",stdout);
    scanf("%s",str+1);
    n=strlen(str+1);
    for(int i=1;i<=n;++i) op[i]=change(str[i]);
    memset(dp,0x3f,sizeof(dp));
    for(int len=1;len<=n;++len)
        for(int l=1;l<=n-len+1;++l)
        {
            int r=l+len-1;
            if(l==r) dp[l][r]=1;
            else if(op[l]==op[r])
                dp[l][r]=min(dp[l+1][r],dp[l][r-1]);
            else
                for(int k=l;k<r;++k)
                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
        }
    printf("%d",dp[1][n]);
    return 0;
}
/*
AAAAA
*/

2.CF1109A Sasha and a Bit of Relax

$date:2022.4.10$

区间数学题，详见题解

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
#define ls p<<1
#define rs ls|1
typedef long long ll;
using namespace std;
const int MAXN=3e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
ll n,val,sum[MAXN];
ll res;
map<pair<ll,ll>,ll>M;
int main()
{
    // freopen("segment.in","r",stdin);
    // freopen("segment.out","w",stdout);
    read(n);
    ++M[make_pair(0,1)];
    for(int i=1;i<=n;++i)
    {
        read(val);
        sum[i]=sum[i-1]^val;
        ll x=!(i&1);
        res+=M[make_pair(sum[i],x)];
        ++M[make_pair(sum[i],x)];
    }
    printf("%lld",res);
    return 0;
}
/*
5
1 2 3 4 5
6
3 2 2 3 7 6

x^x=0
x^0=x
*/

3.P8179 「EZEC-11」Tyres

$date:2022.04.16$

虽然不是随机跳的，但是还是记上吧。调了大半天的。最后发现 $INF$ 开小了。题解的话看出题人就可以了，这里不多说。（主要是讲不明白）。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=505;
const int MAXM=2e5+1;
const ll MAXB=25;
const ll INF=0x3f3f3f3f3f3f3f3f;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
ll n,m;
ll t,dp[MAXN][MAXB+8],g[MAXM],hgt[MAXM];
ll a[MAXN],b[MAXN],c[MAXN],s;
struct Compare
{
    bool operator()(const ll&x,const ll&y)
    {
        return (a[x]+b[x]*c[x]*c[x]>a[y]+b[y]*c[y]*c[y])||
            (a[x]+b[x]*c[x]*c[x]==a[y]+b[y]*c[y]*c[y]&&x>y);
    }
};
priority_queue<ll,vector<ll>,Compare>Q;
int main()
{
    // freopen("t3.in","r",stdin);
    // freopen("t3.out","w",stdout);
    read(n),read(m),read(t),s=0;
    for(ll i=1;i<=n;++i)
    {
        read(a[i]),read(b[i]),c[i]=MAXB,Q.push(i);
        dp[i][1]=a[i]+t;
        for(ll j=2;j<=MAXB;++j)
            dp[i][j]=dp[i][j-1]+a[i]+b[i]*(j-1)*(j-1);
    }
    memset(g,0x3f,sizeof(g)),g[0]=0;
    for(ll i=1;i<=n;++i)
    {
        s=min(m,s+MAXB);
        for(ll j=s;j>=0;--j)
            for(ll k=0;k<=MAXB&&k<=j;++k)
                g[j]=min(g[j],g[j-k]+dp[i][k]);
    }
    for(ll i=1;i<=m;++i)
    {
        ll x=Q.top();
        Q.pop();
        hgt[i]=hgt[i-1]+a[x]+b[x]*c[x]*c[x];
        ++c[x],Q.push(x);
    }
    ll ans=INF;
    for(ll i=0;i<=s&&i<=m;++i) ans=min(ans,g[i]+hgt[m-i]);
    printf("%lld",ans-t);
    return 0;
}
/*
2 4 50
10 100
100 1
*/

4.CF986A Fair

$date:2022.04.16$

看到最短路，我啪的一下就点进来了。这道题类似于全源最短路，但是其点数和边数过大，所以考虑按颜色分配。用 $Dist[c][v]$ 表示到 $c$ 节点涂上 $v$ 颜色的最小代价，然后用 $O(n)$ 的 $bfs$ 跑即可，然后将所有颜色排序，在每个节点处取前 $s$ 个 $Dist_{c,v}$ 即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
const int MAXM=1e5+1;
const int MAXK=101;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int n,m,k,s,cnt[MAXN];
struct edge
{
    int next,to;
}Edge[MAXM<<1];
int Head[MAXN],Total,Dist[MAXN][MAXK];
inline void addEdge(int u,int v)
{
    Edge[++Total]=(edge){Head[u],v};Head[u]=Total;
    Edge[++Total]=(edge){Head[v],u};Head[v]=Total;
}
vector<int>Col[MAXK];
queue<int>Q;
int main()
{
    // freopen("mininum-road.in","r",stdin);
    // freopen("mininum-road.out","w",stdout);
    read(n),read(m),read(k),read(s);
    for(int i=1;i<=n;++i) read(cnt[i]),Col[cnt[i]].push_back(i);
    for(int i=1,u,v;i<=m;++i)
    {
        read(u),read(v);
        addEdge(u,v);
    }
    memset(Dist,-1,sizeof(Dist));
    for(int c=1;c<=k;++c)
    {
        for(auto i:Col[c])
        {
            Q.push(i);
            Dist[i][c]=0;
        }
        while(!Q.empty())
        {
            int u=Q.front();Q.pop();
            for(int e=Head[u],v;e;e=Edge[e].next)
            {
                if(Dist[(v=Edge[e].to)][c]==-1)
                    Dist[v][c]=Dist[u][c]+1,Q.push(v);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        ans=0;
        sort(Dist[i]+1,Dist[i]+1+k);
        for(int j=1;j<=s;++j) ans+=Dist[i][j];
        printf("%d ",ans);
    }
    return 0;
}
/*
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
*/

5.P5810 [SCOI2004]文本的输入

$date:2022.4.19$

并不是随机跳的，无意中刷了一道四川省选题。

一道数学类型的 $dp$ 题。定义 dp[i] 为代价为 $i$ 时的最大字符数，对于添加字符，则 dp[i]=dp[i-1]+1 。而对于复制则遍历 $i-k,k=2j+5,j \in \mathbb{N^*}$ ，然后转移 $dp_i=\max^{k=2j+5 \leq i}_{u=1}(u+1)dp_{i-k}$ 即可。可以证明 dp[i] 单调。二分查找即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=4e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
ll T,dp[MAXN],ans;
int main()
{
    // freopen("o(1).in","r",stdin);
    // freopen("o(1).out","w",stdout);
    read(T);
    if(T==0)
    {
        printf("0");
        return 0;
    }
    for(ans=1;dp[ans-1]<T;++ans)
    {
        dp[ans]=dp[ans-1]+1;
        for(ll i=ans-7,j=2;i>=1;i-=2,++j)
            dp[ans]=max(dp[ans],dp[i]*j);
    }
    printf("%lld",ans-1);
    return 0;
}
/*
20
*/

6.P1934 封印

$date:2022.4.20$

较水的 $dp$ 题，转移方程：$dp_{i}=\min\{dp_{j}+(v_i+v_j)(\sum\limits^{i}_{k=j}v_k)\},v_i+v_j \leq t,j<i$ 初始化 $dp_{i}=dp_{i-1}+n^2v_i$ ，注意开 long long ，要爆。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1001;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int n;
ll val[MAXN],sum[MAXN],dp[MAXN],t;
int main()
{
    // freopen("dp.in","r",stdin);
    // freopen("dp.out","w",stdout);
    read(n),read(t);
    for(re int i=1;i<=n;++i) read(val[i]),sum[i]=sum[i-1]+val[i];
    for(int i=1;i<=n;++i)
    {
        dp[i]=dp[i-1]+n*n*val[i];
        for(int j=i-1;j>=1;--j)
            if(val[i]+val[j]<=t)
                dp[i]=min(dp[i],dp[j-1]+(val[i]+val[j])*(sum[i]-sum[j-1]));
    }
    printf("%lld",dp[n]);
    return 0;
}
/*
6 10
8 5 7 9 3 5
*/

7.P7224 [RC-04] 子集积

$date:2022.4.20$

好吧，刚开始我以为这是一道普普通通的背包，结果是我想错了。果然还是太菜了，看了题解之后才有了点思路，但是还是失败了。就算贺过去了。这里给出题解的思路。

一共有 $2^n$ 个子集，暴力加入每一个物品，然后算就完事了。但是这样的时间复杂度是 $O(nm)$ ，不太保险。所以将 $a_i$ 相同的统一处理。即转换为完全背包。令 $a_i=j(j>1)$ 的 $i$ 有 $k$ 个，则对于 $j,j^2,j^3…j^k$ 的转移系数为 $(^k_q)$ 。如果 $a_i=1$ 则将答案乘以 $2^k$ 而不作转移，最后统一处理。

时间复杂度 $O(\sum\limits^{m}_{i=2}\sum\limits^{cnt_i}_{j=1}\lfloor\frac{m}{i^j}\rfloor)$ ，一个很离谱的式子。近似于 $O(m \ln m)$ 。

预处理阶乘以及逆元以及阶乘的逆元用来求组合数。然后就背包了。

尝试了一下封装写法。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
const int Mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
namespace Calc
{
    inline void add(int &a,int b)
    {
        a=a+b-(a+b>=Mod?Mod:0);
    }
    inline void sub(int &a,int b)
    {
        a=a-b+(a-b<0?Mod:0);
    }
    inline int pro(int a,int b)
    {
        return 1ll*a*b%Mod;
    }
};
int fac[MAXN],inv[MAXN],inv_fac[MAXN],n;
inline void init(int n)
{
    fac[0]=inv_fac[0]=1;
    fac[1]=inv[1]=inv_fac[1]=1;
    for(int i=2;i<=n;++i)
    {
        fac[i]=Calc::pro(fac[i-1],i);
        inv[i]=Calc::pro(Mod-Mod/i,inv[Mod%i]);
        inv_fac[i]=Calc::pro(inv_fac[i-1],inv[i]);
    }
}
inline int C(int n,int m)
{
    if(n<0||m<0||n<m) return 0;
    return Calc::pro(fac[n],Calc::pro(inv_fac[m],inv_fac[n-m]));
}
int m,val[MAXN],dp[MAXN],cnt[MAXN];
int main()
{
    // freopen("dp-bag.in","r",stdin);
    // freopen("dp-bag.out","w",stdout);
    read(n),read(m);
    for(re int i=1;i<=n;++i) read(val[i]),++cnt[val[i]];
    int Max=0;
    for(int i=2;i<MAXN;++i) checkMax(Max,cnt[i]);
    init(Max);
    dp[1]=1;
    for(int i=2;i<MAXN;++i)
        if(cnt[i])
            for(int k=m/i;k>=1;--k)
                if(dp[k])
                {
                    ll v=i;
                    for(int j=1;j<=cnt[i]&&v*k<=m;++j,v*=i)
                        Calc::add(dp[v*k],Calc::pro(C(cnt[i],j),dp[k]));
                }
    int ans=1;
    for(int i=1;i<=n-cnt[1];++i) Calc::add(ans,ans);
    for(int i=1;i<=m;++i) Calc::sub(ans,dp[i]);
    for(int i=1;i<=cnt[1];++i) Calc::add(ans,ans);
    printf("%d",ans); 
    return 0;
}
/*
20 123456
1 5 12 24 189893 233333 2 22 134 3284 28456 261 50 10 1 2 2 2 2 22
*/

8.P7228 [COCI2015-2016#3] MOLEKULE

$date:2022.4.20$

跑一遍 $dfs$ ，然后使其入度和出度相交为 $0$ 即可。毕竟这道题不需要让你输出价值。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
namespace Graph
{
    int Head[MAXN],Total,To[MAXN<<1];
    bool f,vis[MAXN];
    struct edge
    {
        int next,to;
    }Edge[MAXN<<1];
    inline void addEdge(int u,int v)
    {
        Edge[++Total]=(edge){Head[u],v};Head[u]=Total;
        Edge[Total+MAXN]=(edge){Head[v],u};Head[v]=Total+MAXN;
    }
    void dfs(int u)
    {
        if(vis[u]) return ;
        vis[u]=1,f^=1;
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            if(vis[(v=Edge[e].to)]) continue;
            if(e>MAXN) To[e-MAXN]=f^1;
            else To[e]=f;
            dfs(v);
        }
        f^=1;
    }
    inline void outPrint(int n)
    {
        for(int i=1;i<n;++i) printf("%d\n",To[i]);
    }
}
int N;
int main()
{
    // freopen("dfs.in","r",stdin);
    // freopen("dfs.out","w",stdout);
    read(N);
    for(int i=1,u,v;i<N;++i)
    {
        read(u),read(v);
        Graph::addEdge(u,v);
    }
    Graph::dfs(1);
    Graph::outPrint(N);
    return 0;
}
/*
3
1 2
2 3
*/

9.P4763 [CERC2014]Bricks

$date:2022.4.20$

看到同机房巨佬 $Live$ 在切，然后想起以前在学校的 $OI$ 上做过，然后就过来 $experience^2$ 了。一道比较难思考的贪心题。思路也忘了，估计现在也不会打了。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,ans,T;
int val[MAXN],cnt[MAXN],t[MAXN];
char op[MAXN];
inline bool change(char s)
{
    return (s=='B'?1:0);
}
inline void init()
{
    read(N),ans=0;
    memset(op,'\0',sizeof(op));
    memset(cnt,0,sizeof(cnt));
    memset(t,0,sizeof(t));
    for(int i=1;i<=N;++i)
    {
        read(val[i]);
        cin>>op[i];
        cnt[change(op[i])]+=val[i];
    }
}
int main()
{
    // freopen("brick.in","r",stdin);
    // freopen("brick.out","w",stdout);
    read(T);
    while(T--)
    {
        init();
        if(!cnt[0]||!cnt[1])
        {
            printf("%d\n",cnt[0]+cnt[1]);
            continue;
        }
        for(int i=1;i<=N;++i)
        {
            int x=change(op[i]),y=change(op[i])^1;
            if(1ll*cnt[x]*t[y]%cnt[y]==0)
            {
                int res=1ll*cnt[x]*t[y]/cnt[y]-t[x];
                if(res>=1&&res<=val[i]) ++ans;
            }
            t[x]+=val[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
3
3
1 B
3 W
2 B
4
3 W
3 B
9 W
1 B
2
2 W
3 W
*/

10.CF1562C Rings

$date:2022.04.22$

暴力 $O(n^2)$ 查找，但显然是过不了的。所以我们来找数学规律。

由于 $0$ 是任何非 $0$ 整数的倍数，一个数本身也是自己的倍数，所以：

  • 如果该字符串中有大于等于 $\lfloor \frac{n}{2} \rfloor$ 的连续子串全为 $0$ ，那么另找一个长度大于 $\lfloor \frac{n}{2} \rfloor$ 的连续子串即可。
  • 如果该字符串中有两个长度大于等于 $\lfloor \frac{n}{2} \rfloor$ 的连续子串，或者是有一个长度大于等于 $\frac{n}{2}$ 的连续子串且该字串前面一位或数位为 $0$，那么也是一组解。
  • 如果一个字符串有一个长度大于等于 $\lfloor \frac{n}{2} \rfloor$ 的连续子串，它的后面一位或数位为 $0$，说明包括后面的 $0$ 的子串一定是该子串的 $2$ 倍，是一组解。
  • 否则说明该字符串全为 $1$，符合上面的第二种情况。事实上，上面第一种情况也可以归到第二、三两种情况里。

所以，无论什么情况，该题都是有解的，用 $O(n)$ 扫一遍即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int T,n;
char str[MAXN];
int main()
{
    // freopen("rings.in","r",stdin);
    // freopen("rings.out","w",stdout);
    read(T);
    while(T--)
    {
        read(n);
        scanf("%s",str+1);
        bool flag=0;
        for(int i=1;i<=n;++i)
        {
            if(str[i]=='0')
            {
                flag=1;
                if(i>(n>>1)) printf("1 %d 1 %d\n",i,i-1);
                else printf("%d %d %d %d\n",i,n,i+1,n);
                break;
            }
        }
        if(!flag) printf("1 %d 2 %d\n",n-1,n);
    }  
    return 0;
}
/*
7
6
101111
9
111000111
8
10000000
5
11011
6
001111
3
101
30
100000000000000100000000000000
*/

11.P2620 虫洞

$date:2022.4.22-2022.4.23$

一道说难不难，说简单不简单的题。

考点：离散化+建图+最短路

对于这个数轴而言，能够改变答案贡献的只有虫洞，而虫洞的范围 $P \leq 40$ ，所以考虑建图。首先离散化，对于虫洞的起点与终点，有一条单向边 $E(u,v)=0$ ，并构建一个起点 $0$ 和一个终点 $W$ ，一共 $2P+2$ 个节点，对于非 $E(u,v)=0$ 的边，我们用递归处理其边权。因为不能踩到虫洞起点，所以我们需要将起点存储（推荐 set 和 map ），然后避开即可。

然后跑最短路就可以了。用 $Floyd$ 还是 $SPFA$ 或是 $Dijkstra$ 都是可以的，常数极小。

挖坑：一开始使用 vector 来离散，然后就爆了很久，后来换成数组就好了。所以 $Stl$ 能不用尽量不用。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXP=41;
const int INF=0x3fffffff;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int W,S,P,lenP;
int sat[MAXP],fnl[MAXP];
bool path[MAXP][MAXP];
int Dir[MAXP<<4];
std::set<int>St;
namespace Floyd
{
    int Dist[MAXP<<2][MAXP<<2];
    inline void initForEveryTest()
    {
        memset(Dist,0x3f,sizeof(Dist));
    }
    int calcEdge(int u,int v)
    {
        if(u==v) return 0;
        if(St.count(u)) return INF;
        int k=v;
        for(re int i=1;i<=P;++i)
            if(u<sat[i]&&sat[i]<k&&(sat[i]-u)%S==0) k=sat[i];
        while(k!=v&&St.count(k)) --k;
        if(k==u) return INF;
        return calcEdge(k,v)+(k-u+S-1)/S;
    }
    inline void init()
    {
        for(re int i=1;i<lenP;++i)
            for(re int j=i+1;j<=lenP;++j)
                Dist[i][j]=min(Dist[i][j],calcEdge(Dir[i],Dir[j]));
    }
    inline void calc()
    {
        for(re int k=1;k<=lenP;++k)
            for(re int i=1;i<=lenP;++i)
                for(re int j=1;j<=lenP;++j)
                    Dist[i][j]=min(Dist[i][j],Dist[i][k]+Dist[k][j]);
    }
    inline void outPut()
    {
        printf("%d\n",Dist[1][lenP]);
    }
    inline void addEdge(int u,int v,int w)
    {
        Dist[u][v]=w;
    }
};
using namespace Floyd;
int main()
{
    // freopen("dp-graph.in","r",stdin);
    // freopen("dp-graph.out","w",stdout);
    read(W);
    while(W)
    {
        read(S,P);
        St.clear(),lenP=0;
        memset(Dir,0,sizeof(Dir));
        Floyd::initForEveryTest();
        for(re int i=1;i<=P;++i)
        {
            read(sat[i],fnl[i]);
            Dir[++lenP]=sat[i],Dir[++lenP]=fnl[i];
            St.insert(sat[i]);
        }
        Dir[++lenP]=0,Dir[++lenP]=W;
        sort(Dir+1,Dir+1+lenP);
        lenP=unique(Dir+1,Dir+1+lenP)-Dir-1;
        for(re int i=1;i<=P;++i)
        {
            int d1=lower_bound(Dir+1,Dir+1+lenP,sat[i])-Dir;
            int d2=lower_bound(Dir+1,Dir+1+lenP,fnl[i])-Dir;
            Floyd::addEdge(d1,d2,0);
        }
        Floyd::init();
        Floyd::calc();
        Floyd::outPut();
        read(W);
    }
    return 0;
}
/*
28 3 5
2 18
5 13
12 6
17 25
20 15
50 6 1
9 45
0
*/

12.P1879 [USACO06NOV]Corn Fields G

$date:2022.04.24$

经典状压模板题，没啥好讲的。只是因为括号打错位调了很久。太菜了。

今天省选名单出了，在线膜拜省队爷wfy。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=13;
const int MAXM=13;
const int MAXP=1<<14;
const int Mod=1e8;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M;
int Map[MAXN][MAXM],state[MAXP];
int dp[MAXN][MAXP],ok[MAXN];
int main()
{
    // freopen("dp-compression.in","r",stdin);
    // freopen("dp-compression.out","w",stdout);
    read(N,M);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            read(Map[i][j]);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            ok[i]=(ok[i]<<1)+Map[i][j];
    for(int s=0;s<(1<<M);++s)
        state[s]=((s&(s>>1))==0)&&((s&(s<<1))==0);
    dp[0][0]=1;
    for(int i=1;i<=N;++i)
        for(int s=0;s<(1<<M);++s)
            if(state[s]&&((s&ok[i])==s))
                for(int sl=0;sl<(1<<M);++sl)
                    if((s&sl)==0)
                        dp[i][s]=(dp[i][s]+dp[i-1][sl])%Mod;
    int res=0;
    for(int s=0;s<(1<<M);++s)
        res=(res+dp[N][s])%Mod;
    /*for(int i=1;i<=N;++i){
        for(int s=0;s<(1<<M);++s)
            printf("%d ",dp[i][s]);
        printf("%d ",ok[i]);
        puts("");
    }
    for(int s=0;s<(1<<M);++s) printf("%d ",state[s]);
    puts("");*/
    printf("%d",res);
    return 0;
}
/*
2 3
1 1 1
0 1 0
*/

13.CF803D Magazine Ad

$date:2022.4.27$

较 $H_2O$ 的二分题，注意字符串的读入。详见题解

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXS=1e6+1;
const int MAXK=1e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int k,len,p;
char str[MAXS];
int val[MAXS],tot;
inline bool check(int x)
{
    int res=0,cnt=0;
    for(int i=1;i<=tot;++i)
    {
        if(val[i]>x) return 0;
        if(res+val[i]<=x) res+=val[i];
        else ++cnt,res=val[i];
    }
    // printf("%d %d\n",x,cnt);
    if(cnt>=k) return 0;
    return 1;
}
int main()
{
    // freopen("dp.in","r",stdin);
    // freopen("dp.out","w",stdout);
    read(k);
    while((str[++len]=gh())!='\n');
    p=1;
    for(int i=1;i<=len;++i)
        if(str[i]=='-'||str[i]==' ')
            val[++tot]=i-p+1,p=i+1;
    if(p!=len+1) val[++tot]=len-p;
    int l=0,r=len;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d",l);
    return 0;
}
/*
4
garage for sa-le
7 4 3 2
4
Edu-ca-tion-al Ro-unds are so fun
4 3 5 3 3 5 4 3 3
*/

14.P1471 方差

$date:2022.4.28$

好久没有手切过蓝题了

区间维护题，较基础的线段树模板，结合了一点数学知识。

然后维护即可。记得在粘贴代码时改掉函数名。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M;
db val[MAXN];
struct Seg
{
    db val,val2,tag;
    int l,r;
    db sum()
    {
        return 1.0*(r-l+1);
    }
}Tree[MAXN<<2];
inline void pushUp(int p)
{
    Tree[p].val=Tree[p<<1].val+Tree[p<<1|1].val;
    Tree[p].val2=Tree[p<<1].val2+Tree[p<<1|1].val2;
}
inline void pushDown(int p)
{
    if(Tree[p].tag)
    {
        Tree[p<<1].val2+=(Tree[p<<1].val*Tree[p].tag)*2+Tree[p<<1].sum()*Tree[p].tag*Tree[p].tag;
        Tree[p<<1|1].val2+=(Tree[p<<1|1].val*Tree[p].tag)*2+Tree[p<<1|1].sum()*Tree[p].tag*Tree[p].tag;
        Tree[p<<1].val+=Tree[p<<1].sum()*Tree[p].tag;
        Tree[p<<1|1].val+=Tree[p<<1|1].sum()*Tree[p].tag;
        Tree[p<<1].tag+=Tree[p].tag,Tree[p<<1|1].tag+=Tree[p].tag;
        Tree[p].tag=0;
    }
}
void build(int p,int l,int r)
{
    Tree[p].l=l,Tree[p].r=r;
    if(l==r)
    {
        Tree[p].val=val[l];
        Tree[p].val2=val[l]*val[r];
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    pushUp(p);
}
void modify(int p,int l,int r,db d)
{
    if(l<=Tree[p].l&&Tree[p].r<=r)
    {
        Tree[p].val2+=(Tree[p].val*d)*2+Tree[p].sum()*d*d;
        Tree[p].val+=Tree[p].sum()*d;
        Tree[p].tag+=d;
        return ;
    }
    pushDown(p);
    int mid=(Tree[p].l+Tree[p].r)>>1;
    if(l<=mid) modify(p<<1,l,r,d);
    if(mid<r) modify(p<<1|1,l,r,d);
    pushUp(p);
}
db queryAverage(int p,int l,int r)
{
    if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].val;
    int mid=(Tree[p].l+Tree[p].r)>>1;
    db val=0;
    pushDown(p);
    if(l<=mid) val+=queryAverage(p<<1,l,r);
    if(mid<r) val+=queryAverage(p<<1|1,l,r);
    return val;
}
db queryVariance(int p,int l,int r)
{
    if(l<=Tree[p].l&&Tree[p].r<=r) return Tree[p].val2;
    int mid=(Tree[p].l+Tree[p].r)>>1;
    db val=0;
    pushDown(p);
    if(l<=mid) val+=queryVariance(p<<1,l,r);
    if(mid<r) val+=queryVariance(p<<1|1,l,r);
    return val;
}
int main()
{
    // freopen("segmentbit.in","r",stdin);
    // freopen("segmentbit.out","w",stdout);
    read(N,M);
    for(re int i=1;i<=N;++i) scanf("%lf",&val[i]);
    build(1,1,N);
    while(M--)
    {
        int op,ql,qr;
        read(op,ql,qr);
        if(op==1)
        {
            db qk;
            scanf("%lf",&qk);
            modify(1,ql,qr,qk);
        }
        else if(op==2) printf("%.4lf\n",queryAverage(1,ql,qr)/(qr-ql+1));
        else
        {
            db x1=queryAverage(1,ql,qr),x2=queryVariance(1,ql,qr);
            db res=x2+(qr-ql+1)*(x1/(qr-ql+1))*(x1/(qr-ql+1))-2*(x1/(qr-ql+1))*x1;
            printf("%.4lf\n",res/(qr-ql+1));
        }
    }
    return 0;
}
/*
5 5
1 5 4 2 3
2 1 4
3 1 5
1 1 1 1
1 2 2 -1
3 1 5
*/

15.P4162 [SCOI2009]最长距离

$date:2022.05.06$

建图，将 $nm$ 的矩阵转化为一个有 $nm$ 个点的图，$c(i,j)=(map[j]=1)?1:0$ 即可，然后每到一个点记录一次答案记为 $res=\max\{res,calc(s,k)\}$ 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=31;
const int INF=0x7f7f7f7f;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int dx[]={0,1,-1,0,0};
const int dy[]={0,0,0,1,-1};
int N,M,T;
char Map[MAXN][MAXN];
int Start[MAXN*MAXN];
db Dist[MAXN*MAXN][MAXN*MAXN],res;
char ch;
inline int getId(int i,int j)
{
    return (i-1)*M+j;
}
inline db calc(db x,db y)
{
    return sqrt(x*x+y*y);
}
struct edge
{
    int next,to,val;
}Edge[MAXN*MAXN*MAXN*MAXN<<2];
int Head[MAXN*MAXN],Total;
inline void addEdge(int u,int v,int w)
{
    Edge[++Total]=(edge){Head[u],v,w};Head[u]=Total;
    // Edge[++Total]=(edge){Head[v],u,w};Head[v]=Total;
}
int Dir[MAXN*MAXN];
bool Vis[MAXN*MAXN];
inline void spfa(int s)
{
    for(int i=1;i<=N*M;++i) Dir[i]=INF,Vis[i]=0;
    Dir[s]=Start[s],Vis[s]=1;
    queue<int>Q;
    Q.push(s);
    // printf("start from %d with %d\n",s,Dir[s]);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        checkMax(res,Dist[s][u]);
        Vis[u]=0;
        for(int e=Head[u],v;e;e=Edge[e].next)
        {
            v=Edge[e].to;
            // printf("road from %d to %d\n",u,v);
            if(Dir[v]>Dir[u]+Edge[e].val)
            {
                Dir[v]=Dir[u]+Edge[e].val;
                // printf("from %d to %d spend %d\n",u,v,Dir[v]);
                if(!Vis[v]&&T>=Dir[v])
                {
                    Vis[v]=1;
                    Q.push(v);
                }
            }
        }
    }
    return ;
}
int main()
{
    // freopen("min-road.in","r",stdin);
    // freopen("min-road.out","w",stdout);
    read(N,M,T);
    for(re int i=1;i<=N;++i) scanf("%s",Map[i]+1);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=N;++j)
            for(int k=1;k<=M;++k)
                for(int l=1;l<=M;++l)
                    Dist[getId(i,k)][getId(j,l)]=calc(i-j,k-l);
    /*for(int i=1;i<=N;++i){
        for(int j=1;j<=M;++j)
            printf("%d ",getId(i,j));
        puts("");
    }
    return 0;*/
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
        {
            Start[getId(i,j)]=Map[i][j]-'0';
            for(int k=1,w;k<=4;++k)
            {
                int nx=i+dx[k],ny=j+dy[k];
                if(nx<1||nx>N||ny<1||ny>M) continue;
                w=Map[nx][ny]-'0';
                addEdge(getId(i,j),getId(nx,ny),w);
            }
        }
    for(int i=1;i<=N*M;++i) spfa(i);
    printf("%.6lf",res);
    return 0;
}
/*
3 3 0
001
001
110
*/

16.P6870 [COCI2019-2020#5] Zapina

$date:2022.05.06$

数学dp ，组合数学题。

杨辉三角求组合数： $C(n,m)=C(n-1,m)+C(n-1,m-1)$

转移方程：

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=351;
const int Mod=1e9+7;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,dp[MAXN][MAXN],C[MAXN][MAXN];
inline int quickPow(ll a,int b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%Mod;
        a=a*a%Mod;
        b>>=1;
    }
    return res;
}
inline void init()
{
    for(int i=0;i<=N;++i)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
    }
    dp[1][1]=1;
    /*for(int i=0;i<=N;++i){
        for(int j=0;j<=i;++j)
            printf("%d ",C[i][j]);
        puts("");
    }*/
}
int main()
{
    // freopen("dp.in","r",stdin);
    // freopen("dp.out","w",stdout);
    read(N);
    init();
    for(int i=2;i<=N;++i)
        for(int j=1;j<=N;++j)
        {
            if(j>=i) dp[i][j]=1ll*C[j][i]*quickPow(i-1,j-i)%Mod;
            for(int k=0;k<=j;++k)
                if(i!=k) dp[i][j]=(dp[i][j]+1ll*C[j][k]*dp[i-1][j-k])%Mod;
        }
    printf("%d",dp[N][N]%Mod);
    return 0;
}
/*
1
2
314
*/

17.CF1119B Alyona and a Narrow Fridge

$date:2022.05.06$

很玄学的一道题，样例看不懂，题解不明白。

more and more vegetables, what should I do?

贺过去了，二分 $+$ 贪心。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e3+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int H,N,hgt[MAXN];
vector<int>V;
inline bool cmp(int a,int b)
{
    return a>b;
}
inline bool check(int x)
{
    V.clear();
    for(int i=1;i<=x;++i) V.push_back(hgt[i]);
    sort(V.begin(),V.end(),cmp);
    int maxn=0;
    for(int i=0,pos1,pos2;i<V.size();++i)
    {
        if((i+1)&1)
        {
            pos1=maxn+V[i];
            if(pos1>H) return 0;
        }
        else
        {
            pos2=maxn+V[i];
            if(pos2>H) return 0;
            maxn=max(pos1,pos2);
        }
    }
    return 1;
}
int main()
{
    // freopen("dp?.in","r",stdin);
    // freopen("dp?.out","w",stdout);
    read(N,H);
    for(re int i=1;i<=N;++i) read(hgt[i]);
    int l=1,r=N+1;
    while(l<r-1)
    {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%d",l);
    return 0;
}
/*
5 7
2 3 5 4 1
*/

18.P7159 「dWoi R1」Sweet Fruit Chocolate

$date:2022.5.27$

简单的树形 dp 问题，时间复杂度 $\mathcal O(n)$

计算方程 $ans=\sum^{n}_{i=1}d_ia_i$ ，记 $d_i$ 为第 $i$ 个点到根节点的距离。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
const int Mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N;
ll num[MAXN],dp[MAXN],ans;
struct edge
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(edge){Head[u],v};Head[u]=Total;
    Edge[++Total]=(edge){Head[v],u};Head[v]=Total;
}
void dpTree(int x,int last)
{
    dp[x]=dp[last]+1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dpTree(v,x);
    }
}
inline ll powFast(ll a,int b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%Mod;
        a=a*a%Mod;
        b>>=1;
    }
    return res%Mod;
}
int main()
{
    // freopen("tree.in","r",stdin);
    // freopen("tree.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(num[i]);
    for(int i=1,u,v;i<N;++i)
    {
        read(u,v);
        addEdge(u,v);
    }
    dpTree(1,0);
    ll Cnt=powFast(2ll,N-1);
    for(int i=1;i<=N;++i)
        ans=(ans+dp[i]*num[i])%Mod;
    printf("%lld",ans*Cnt%Mod);
    return 0;
}
/*
3
1 1 2
1 2
2 3
*/

19.CF747B Mammoth’s Genome Decoding

$date:2022.5.27$

暴力，暴力，暴力。甚至懒得优化。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e4+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,num[5];
char str[MAXN],res[MAXN];
inline int change(char s)
{
    if(s=='A') return 1;
    if(s=='C') return 2;
    if(s=='G') return 3;
    if(s=='T') return 4;
}
inline char back(int s)
{
    if(s==1) return 'A';
    if(s==2) return 'C';
    if(s==3) return 'G';
    if(s==4) return 'T';
}
inline int comMin()
{
    int id=1,res=1e9;
    if(num[1]<res) res=num[1],id=1;
    if(num[2]<res) res=num[2],id=2;
    if(num[3]<res) res=num[3],id=3;
    if(num[4]<res) res=num[4],id=4;
    return id;
}
int main()
{
    // freopen("AGCT.in","r",stdin);
    // freopen("AGCT.out","w",stdout);
    read(N);
    scanf("%s",str+1);
    for(int i=1;i<=N;++i) if(str[i]!='?') ++num[change(str[i])];
    for(int i=1;i<=N;++i)
        if(str[i]=='?')
        {
            int s=comMin();
            res[i]=back(s);
            ++num[s];
        }
        else res[i]=str[i];
    int numMin=min(num[1],min(num[2],min(num[3],num[4])));
    int numMax=max(num[1],max(num[2],max(num[3],num[4])));
    if(numMin!=numMax) printf("===");
    else for(int i=1;i<=N;++i) printf("%c",res[i]);
    return 0;
}
/*
8
AG?C??CT
*/

20.CF1136A Nastya Is Reading a Book

$date:2022.6.16$

超级大水题。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=101;
const int MAXP=1e4+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,l[MAXN],r[MAXN],K;
int main()
{
    // freopen("cf.in","r",stdin);
    // freopen("cf.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(l[i],r[i]);
    read(K);
    for(int i=1;i<=N;++i)
        if(l[i]<=K&&K<=r[i])
        {
            printf("%d",N-i+1);
            return 0;
        }
    return 0;
}
/*

*/

21.P3912 素数个数

$date:2022.6.16$

线性筛质数模板题。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e8+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,Total,pri[MAXN];
bool ok[MAXN];
inline void init(int MaxN)
{
    memset(ok,1,sizeof(ok));
    ok[1]=0;
    for(int i=2;i<=MaxN;++i)
    {
        if(ok[i]) pri[++Total]=i;
        for(int j=1;j<=Total&&i*pri[j]<=MaxN;++j)
        {
            ok[i*pri[j]]=0;
            if(i%pri[j]==0) break;
        }
    }
    printf("%d",Total);
}
int main()
{
    // freopen("xor.in","r",stdin);
    // freopen("xor.out","w",stdout);
    read(N);
    init(N);
    return 0;
}
/*

*/

22.P5131 荷取融合

$date:2022.6.16$

常规 dp 题。

用 $dp_{i,j}$ 表示前 $i$ 个中选了 $j$ 个的方案数，用 $g_{i,j}$ 表示相应的贡献总和。

转移方程：

$dp_{i,j}=dp_{i-1,j}+dp_{i,j-1}$

$g_{i,j}=g_{i-1,j}+g_{i,j-1}\times val_i$

最终答案：

$\frac{g_{n,k}}{f_{n,k}}$

快速幂求逆元即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
const int MAXK=3e2+1;
const int Mod=19260817;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,K,val[MAXN],dp[2][MAXK],g[2][MAXK];
bool ok;
inline int qPow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1ll*res*a%Mod;
        a=1ll*a*a%Mod;
        b>>=1;
    }
    return res;
}
int main()
{
    // freopen("math.in","r",stdin);
    // freopen("math.out","w",stdout);
    read(N,K);
    for(int i=1;i<=N;++i) read(val[i]);
    dp[!ok][0]=1;
    for(int i=1;i<=N;++i)
    {
        dp[ok][0]=1;
        for(int j=1;j<=K;++j) dp[ok][j]=(dp[!ok][j]+dp[ok][j-1])%Mod;
        g[ok][0]=1;
        for(int j=1;j<=K;++j) g[ok][j]=(1ll*g[!ok][j]+1ll*g[ok][j-1]*val[i])%Mod;
        ok^=1;
    }
    printf("%d",1ll*g[!ok][K]*qPow(dp[!ok][K],Mod-2)%Mod);
    return 0;
}
/*
3 2
3 1 2
*/

23.P5997 [PA2014]Pakowanie

$date:2022.6.16$

状压 dp 题，贺过去的。不太能理解，看题解，或者自己做吧。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=25;
const int MAXS=(1<<25)+1;
const int MAXM=101;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,dp[MAXS],dw[MAXS];
int wgt[MAXN],cpy[MAXM];
inline bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    // freopen("bag?.in","r",stdin);
    // freopen("bag?.out","w",stdout);
    read(N,M);
    for(re int i=1;i<=N;++i) read(wgt[i]);
    for(re int i=1;i<=M;++i) read(cpy[i]);
    sort(cpy+1,cpy+1+M,cmp);
    for(int i=1;i<(1<<N);++i) dp[i]=M+1;
    for(int s=0;s<(1<<N);++s)
        for(int j=1;j<=N;++j)
            if(s&(1<<(j-1)))
            {
                int up=s^(1<<(j-1));
                if(dw[up]>=wgt[j])
                {
                    if(dp[s]>dp[up]||(dp[s]==dp[up]&&dw[up]-wgt[j]>dw[s]))
                    {
                        dp[s]=dp[up];
                        dw[s]=dw[up]-wgt[j];
                    }
                }
                else if(cpy[dp[up]+1]>=wgt[j])
                {
                    if(dp[s]>dp[up]+1||(dp[s]==dp[up]+1&&cpy[dp[up]+1]-wgt[j]>dw[s]))
                    {
                        dp[s]=dp[up]+1;
                        dw[s]=cpy[dp[up]+1]-wgt[j];
                    }
                }
            }
    if(dp[(1<<N)-1]>=M+1) printf("NIE");
    else printf("%d",dp[(1<<N)-1]);
    return 0;
}
/*

*/

24.CF1512E Permutation by Sum

$date:2022.6.16$

一道思路很简单的题，转化为，给定两个数 $s,k$ 求构造一个数列 $\sum\limits^{s}_{i=1}a_i=k,\forall i,j,a_i \neq a_j$ 即可。

重点在于如何构造，亲测暴力构造会爆，所以使用贪心。详情查看题解。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=501;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int Test,N,Ql,Qr,Qsum;
int Max[MAXN],Min[MAXN],pos,path[MAXN];
bool vis[MAXN],flag;
int main()
{
    // freopen("sum.in","r",stdin);
    // freopen("sum.out","w",stdout);
    read(Test);
    while(Test--)
    {
        read(N,Ql,Qr,Qsum);
        memset(vis,0,sizeof(vis));
        int left=Qr-Ql+1,l=Ql;
        // printf("%d %d\n",((Qr-Ql+1)*(Qr-Ql+2)/2),((Qr-Ql+1)*(N+N+Ql-Qr)/2));
        Max[0]=Min[0]=0;
        for(int i=1;i<=N;++i)
        {
            Min[i]=(i+1)*i/2;
            Max[i]=(N+N-i+1)*i/2;
        }
        for(int i=1;i<=N;++i) vis[i]=0;
        for(int i=1;i<=N;++i)
            if(Qsum-i>=Min[left-1]&&Qsum-i<=Max[left-1])
            {
                path[l++]=i;--left;
                Qsum-=i;vis[i]=1;
            }
        if(l!=Qr+1) printf("-1\n");
        else
        {
            int End=0;
            for(int i=1;i<=N;++i)
                if(!vis[i])
                {
                    if(End==Ql-1) End=Qr;
                    path[++End]=i;
                }
            for(int i=1;i<=N;++i) printf("%d ",path[i]);
            puts("");
        }
    }
    return 0;
}
/*
sum=(a1+an)n/2

n-(qr-ql) ... n
*/

25.P5017 [NOIP2018 普及组] 摆渡车

$date:2022.6.16$

一道其实很早以前就像做了，但是因为实力和时间的原因一直在咕。

斜率优化的经典题之一。

记 $dp_{i}$ 表示第 $i$ 刻时间的最小等待时间，$cnt_i$ 为第 $i$ 刻时间的人数，$sum_i$ 表示来到的时间和。

斜率式：

$dp_j+sum_j=i\times cnt_j+(dp_i-cnt_i\times i+sum_i)$

即可。

可惜琢磨了半天什么都没有想出来，然后又贺了。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=501;
const int MAXT=4e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,T,waiting_Time;
int dp[MAXT],cnt[MAXT],sum[MAXT];
int Que[MAXT<<1];
inline db slope(int i,int j)
{
    return (db)(dp[j]+sum[j]-dp[i]-sum[i])/(cnt[i]==cnt[j]?1e-9:cnt[j]-cnt[i]);
}
int main()
{
    // freopen("slope.in","r",stdin);
    // freopen("slope.out","w",stdout);
    read(N,M);
    for(re int i=1;i<=N;++i)
    {
        read(waiting_Time);T=max(T,waiting_Time);
        ++cnt[waiting_Time],sum[waiting_Time]+=waiting_Time;
    }
    for(int i=1;i<T+M;++i) cnt[i]+=cnt[i-1],sum[i]+=sum[i-1];
    int head=1,tail=0;
    for(int i=0;i<T+M;++i)
    {
        if(i-M>=0)
        {
            while(head<tail&&slope(Que[tail-1],Que[tail])>=slope(Que[tail],i-M)) --tail;
            Que[++tail]=i-M;
        }
        while(head<tail&&slope(Que[head],Que[head+1])<=i) ++head;
        int j=Que[head];
        dp[i]=cnt[i]*i-sum[i];
        if(head<=tail)
            dp[i]=min(dp[i],dp[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
    }
    int ans=1e9;
    for(int i=T;i<T+M;++i) ans=min(ans,dp[i]);
    printf("%d",ans);
    return 0;
}
/*
5 5 
11 13 1 5 5 
*/

26.CF987C Three displays

$\text{date:2022.6.16}$

线段树优化dp ，因为数据过水不需要优化。

暴力 dp 时间复杂度 $\mathcal O(n^2)$ 勉强能过，优化后复杂度 $\mathcal O(n\log n)$ ，Live 巨佬应该会打，也可以看题解，我只会暴力。

记着不要把题看错了，也不要完全相信翻译，适量读读原文。

暴力AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=3e3+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,Min1=1e9,Min2=1e9,Min3=1e9;
struct Display
{
    int s,c;
}Num[MAXN];
int dp[MAXN][4];
int main()
{
    // freopen("math.in","r",stdin);
    // freopen("math.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(Num[i].s);
    for(int i=1;i<=N;++i) read(Num[i].c);
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=N;++i)
        for(int j=1;j<=3;++j)
            for(int k=0;k<i;++k)
                if(Num[i].s>Num[k].s)
                    dp[i][j]=min(dp[i][j],dp[k][j-1]+Num[i].c);
    if(dp[N][3]==1061109567) printf("-1");
    else
    {
        int ans=1e9;
        for(int i=3;i<=N;++i) checkMin(ans,dp[i][3]);
        printf("%d",ans);
    }
    return 0;
}
/*
5
2 4 5 4 10
40 30 20 10 40
10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13
*/

27.SP1030 EIGHTS - Triple Fat Ladies

$\text{date:2022.8.26}$

时隔多日终于还是回来惹。

因为发现自己实力真的不足，所以根本不敢随机题目，就算随机了也最后还是看着题解做，这样没什么太大意思。

这道题而言，看到大的离谱的数据，就知道肯定要找规律。

因为只是看最后三位，所以前面的根本不看。我们把 $1000$ 以内的数据打表，发现只有尾数为 $192,442,692,942$ 的满足条件，之后的就是在千位依次增加。

那么，答案就是 $1000\lfloor\frac{k-1}{4}\rfloor+ans[((k-1)\bmod 4+1)],ans[]=\{192,442,692,942\}$ 。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Test;
ll k;
int ans[]={0,192,442,692,942};
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(Test);
    while(Test--)
    {
        read(k);
        if(k<=4) write(ans[k],'\n');
        else write((k-1)/4,ans[(k-1)%4+1],'\n');
    }
    return 0;
}
/*
192 442 692 942
*/

28.CF1203C Common Divisors

$\text{date:2022.8.30}$

小清新数筛题。

首先发现一个显然的结论，所有满足的数都是满足的数中的最大数的约数，那么题目转换为，求出整个数列的最大公约数的约数个数。

然后一波线性 $\gcd$ ，时间复杂度 $\mathcal O(n\log n)$ ，然后直接枚举约数时间复杂度 $\mathcal O(\sqrt n)$ ，特判一下是不是平方数即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int MAXN=4e5+10;
int N;
ll Gcd,ans;
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i)
    {
        ll x;read(x);
        if(i==1) Gcd=x;
        else Gcd=gcd(Gcd,x);
    }
    for(ll i=1;i*i<=Gcd;++i)
    {
        if(i*i==Gcd) --ans;
        if(Gcd%i==0) ans+=2;
    }
    write(ans);
    return 0;
}
/*
6
6 90 12 18 30 18
*/

29.CF702C Cellular Network

$\text{date:2022.8.30}$

手写二分容易炸锅不是传说。

手写二分还真容易炸锅，考虑人类智慧贪心，然后对于每一座城市，找到左边离它最近的基站和右边离它最近的基站，求两个中较小值的最大值即可。需要建立两个哨兵 $\pm inf$ 。这个哨兵需要满足 $|inf|\geq 3\times 10^9$ 。

因为已经是非严格递增输入了，所以就不需要再次排序了。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int MAXN=1e5+10;
const ll INF=0x1145141919810;
int N,M;
ll Val[MAXN],Pos[MAXN],ans;
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);
    Pos[0]=-INF,Pos[M+1]=INF;
    for(int i=1;i<=N;++i) read(Val[i]);
    for(int i=1;i<=M;++i) read(Pos[i]);
    for(int i=1;i<=N;++i)
    {
        ll l=1,r=M+1,res,x=Val[i];
        while(l<=r)
        {
            ll mid=(l+r)>>1;
            if(Pos[mid]>=x) res=mid,r=mid-1;
            else l=mid+1;
        }
        checkMax(ans,std::min(Pos[res]-x,x-Pos[res-1]));
    }
    write(ans);
    return 0;
}
/*
5 3
1 5 10 14 17
4 11 15
10 10
1 1 2 2 2 4 4 6 7 9
0 1 3 3 3 6 7 8 9 10
*/
相关文章