9/30-10/1

接下来的2个月的方向：
1.每周两场的ICPC区域赛vp，赛后补题，看情况尽量补
2.洛谷上近几年来的省选题，从绿到蓝到紫，一路刷上去
3.多思考，不追求题目的数量，质量才是关键。
4.触类旁通，碰到一个题不会做，一定要去搜寻多个同类型的题目。
5.手速不是拿牌的关键。
6.剩下的就是努力，抓紧时间，有耐力得走完这两个月。

---

I Steadily Growing Steam

参考了大佬的博客。
感觉这个状态的设计很常规，但为什么自己就像不到呢。
在题意上需要注意一个点：
在玩游戏之前，选出一个序列，数量不大于k，将他们t[i]变成之前的2倍，要求在玩游戏的多次回合中两堆牌点数相同，要求价值最大。

做的时候看出是个背包，配合队友应该能写出来的。
分析：
滚动数组的使用。只涉及前一个状态，可借用&判别奇偶，利用^取上一个状态。
前i张牌 最多使用j次技能 两个牌堆差值为k时获得的最大价值是多少
不选这张牌 f[i][j][k]=f[i-1][j][k]
选入放入a堆 f[x][j][k]=max(f[x][j][k],f[x^1][j][k+t[i]]+v[i])
选入放入b堆 f[x][j][k]=max(f[x][j][k],f[x^1][j][k-t[i]]+v[i])
选入加倍后放入a堆
： f[x][j][k]=max(f[x][j][k],f[x^1][j-1][k+2*t[i]]+v[i])
选入加背后放入b堆
： f[x][j][k]=max(f[x][j][k],f[x^1][j-1][k-2*t[i]]+v[i])

#include 
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int inf=1e18;
const int N=7e5+5;
int n,m,f[2][105][5205],v[105],t[105];
//前i张牌 最多使用j次技能 两个牌堆差值为k时获得的最大价值是多少
//不选这张牌  f[i][j][k]=f[i-1][j][k]
//选入放入a堆 f[i][j][k]=f[i][j][k+a[i]]+v[i]
//选入放入b堆 f[i][j][k]=f[i][j][k-a[i]]+v[i]
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>t[i];
    for(int i=0;i<=m;i++)
        for(int j=0;j<=5200;j++) f[0][i][j]=f[1][i][j]=-inf;
    for(int i=0;i<=m;i++)
        for(int j=0;j<=5200;j++) f[0][i][2600]=0;
    for(int i=1;i<=n;i++)     //多张牌
    {
        for(int j=0;j<=m;j++) //加倍次数
        {
            for(int k=0;k<=5200;k++)
            {
                int x=i&1;
                f[x][j][k]=f[x^1][j][k];
                if(k+t[i]<=5200)
                    f[x][j][k]=max(f[x][j][k],f[x^1][j][k+t[i]]+v[i]);
                if(k>=t[i])
                    f[x][j][k]=max(f[x][j][k],f[x^1][j][k-t[i]]+v[i]);
                if(!j) continue;
                if(k+2*t[i]<=5200)
                    f[x][j][k]=max(f[x][j][k],f[x^1][j-1][k+2*t[i]]+v[i]);
                if(k>=2*t[i])
                    f[x][j][k]=max(f[x][j][k],f[x^1][j-1][k-2*t[i]]+v[i]);
            }
        }
    }
    cout<<f[n&1][m][2600]<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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

上海网赛 J - Stone game

两个难想得思维点。
1.虽然说每个石头都面临选和不选两个情况，但是要从那个公式想到01背包还是有点思维量的。
2.第二个难点在于排序，要想到从大到小排序。因为第i块石头若取完后，重量若满足条件，则可以累加上答案dp[j-a[i]]的方案数。

#include 
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int inf=1e18;
const int N=7e5+5;
const int mod=1e9+7;
int n,m,dp[N],a[N],ans;
bool cmp(int a,int b){return a>b;}
void solve()
{
    memset(dp,0,sizeof dp);
    ans=0;
    cin>>n;
    int g=0;
    for(int i=1;i<=n;i++) cin>>a[i],g+=a[i];
    sort(a+1,a+n+1,cmp);
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=g;j>=a[i];j--)
        {
            dp[j]=(dp[j]+dp[j-a[i]])%mod;
            if(j>=g-j&&j-a[i]<=g-j)
                ans=(ans+dp[j-a[i]])%mod;
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    //ios;
    int T;cin>>T;
    while(T--)
        solve();
    return 0;
}

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

P5329 [SNOI2019]字符串

思路：几个操作需要实现。
根据样例便可以看出：
1.若一个字符大于前一个字符，则将这一段下标放到数组尾部；
2.若一个字符小于前一个字符，则前其放到数组的前端尾部。

#include 
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int inf=1e18;
const int N=7e6+5;
const int mod=1e9+7;
bool cmp(int a,int b){return a>b;}
int n,a[N];
string s;
void solve()
{
    cin>>n>>s;
    s=" "+s;
    int l=0,r=n+1,g=1;
    for(int i=2;i<=n;i++)
    {
        if(s[i]==s[i-1]) continue;
        if(s[i]>s[i-1])
        {
            for(int j=i-1;j>=g;j--)
                a[--r]=j;
            g=i;
        }
        else
        {
            for(int j=g;j<=i-1;j++)
                a[++l]=j;
            g=i;
        }
    }
    //cout<
    for(int i=g;i<=n;i++) a[++l]=i;
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}
signed main()
{
    //ios;
    //int T;cin>>T;
    //while(T--)
        solve();
    return 0;
}

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

C. Insertion Sort

四种情况讨论分析，也可打表直接找规律。

#include 
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int inf=1e18;
const int N=7e6+5;
const int mod=1e9+7;
bool cmp(int a,int b){return a>b;}
int n,k,q;

signed main()
{
    //ios;
    int tt=0;
    int T;cin>>T;
    while(T--)
    {
        cin>>n>>k>>q;
        int ans=1;
        if(n<=k)
        {
            for(int i=1;i<=n;i++) ans=ans*i%q;  //第一种情况
            cout<<"Case #"<<++tt<<": "<<ans<<endl;continue;
        }
        for(int i=1;i<=k;i++) ans=ans*i%q;  
        ans=ans*((n-k)*(n-1)+1)%q;
        cout<<"Case #"<<++tt<<": "<<ans<<endl;
    }
    return 0;
}

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

J. How Much Memory Your Code Is Using?

模拟题。接受一行数据后，要注意接受换行符。

#include 
#define int long long
#define endl '\n'
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int inf=1e18;
const int N=7e6+5;
const int mod=1e9+7;
bool cmp(int a,int b){return a>b;}
int n,g;
char c[105];
void solve()
{
    g++;
    cin>>n;
    getchar();
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        string s;
        getline(cin,s);
        if(s.substr(0,4)=="bool"||s.substr(0,4)=="char")
        {
            string ss="";
            int flag=0;
            for(int j=5;j<s.length();j++)
            {
                if(s[j]=='[') flag=1;
                if(s[j]>='0'&&s[j]<='9'&&flag) ss+=s[j];
            }
            if(ss=="")
                ans+=1;
            else
                ans+=stoi(ss);
        }
        else if(s.substr(0,3)=="int"||s.substr(0,5)=="float")
        {
            string ss="";
            int flag=0;
            for(int j=5;j<s.length();j++)
            {
                if(s[j]=='[') flag=1;
                if(s[j]>='0'&&s[j]<='9'&&flag) ss+=s[j];
            }
            if(ss=="")
                ans+=4;
            else
                ans+=4*stoi(ss);
        }
        else if(s.substr(0,6)=="double"||s.substr(0,9)=="long long")
        {
            string ss="";
            int flag=0;
            for(int j=5;j<s.length();j++)
            {
                if(s[j]=='[') flag=1;
                if(s[j]>='0'&&s[j]<='9'&&flag) ss+=s[j];
            }
            if(ss=="")
                ans+=8;
            else
                ans+=8*stoi(ss);
        }
        else if(s.substr(0,11)=="long double"||s.substr(0,8)=="__int128")
        {
            string ss="";
            int flag=0;
            for(int j=5;j<s.length();j++)
            {
                if(s[j]=='[') flag=1;
                if(s[j]>='0'&&s[j]<='9'&&flag) ss+=s[j];
            }
            if(ss=="")
                ans+=16;
            else
                ans+=16*stoi(ss);
        }
        //cout<<"gg"<
    }
    ans=ceil(ans*1.0/1024);
    cout<<"Case #"<<g<<": "<<ans<<endl;
}
signed main()
{
    //ios;
    int T;cin>>T;
    while(T--)
        solve();
    return 0;
}

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