打表+dp思维+博弈

E. Sending a Sequence Over the Network

应该属于一个经典dp，可惜我没做出来。。。
思路：对于一个数字来说，它可以向左扩展，也可以向有扩展。
设计状态:f[i]表示第i位数字能否成功被包括
先讨论f[i]是否和法，由状态f[i-a[i]-1]转移得到；只有f[i]被表示时，才可将a[i+1]向右扩展。

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=2e5+5;
const int inf=1e18;
const int mod=998244353;
int n,a[N],f[N];

void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin>>a[i],f[i]=0;
    f[0]=1;
    for(int i=0;i<=n;i++)
    {
        if(i-a[i]-1>=0&&f[i-a[i]-1]) f[i]=1;
        if(!f[i]) continue;
        if(i+a[i+1]+1<=n&&f[i]) f[i+a[i+1]+1]=1;
    }
    if(f[n]) cout<<"YES"<<endl;
    else
        cout<<"NO"<<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

C. Chef Monocarp

思路：KM算法求完美匹配的最大权值，左部点和右部点要求个数相同。
对于本题，左部点为烘培时间，右部点为拿出时间，因为拿出时间的不固定，构建虚点，连线权值要求为0，否则会对答案产生贡献。
由于是最小权值，转化为负值，边初始化为-inf，跑KM算法.

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=405;
const int inf=1e18;
const int mod=998244353;
int n,a[N];
int w[N][N],lx[N],ly[N];
bool visx[N],visy[N];
int match[N],delta,c[N],p[N];
int A[N],P[N],B[N],C[N];
void bfs(int x)         // O(n^3)的KM板子
{
    int a,y=0,y1=0;
    for(int i=1;i<=n;i++) p[i]=0,c[i]=inf;
    match[y]=x;
    do{
        a=match[y],delta=inf,visy[y]=1;
        for(int b=1;b<=n;b++)
        {
            if(!visy[b])
            {
                if(c[b]>lx[a]+ly[b]-w[a][b])
                    c[b]=lx[a]+ly[b]-w[a][b],p[b]=y;
                if(c[b]<delta) delta=c[b],y1=b;
            }
        }
        for(int b=0;b<=n;b++)
            if(visy[b]) lx[match[b]]-=delta,ly[b]+=delta;
            else c[b]-=delta;
        y=y1;
    }while(match[y]);
    while(y)
        match[y]=match[p[y]],y=p[y];
}
int KM()
{
    for(int i=1;i<=n;i++) match[i]=lx[i]=ly[i]=0;
    for(int i=1;i<=n;i++)
    {
        for(int i=0;i<=n;i++) visy[i]=0;
        bfs(i);
    }
    int res=0;
    for(int i=1;i<=n;i++) res+=w[match[i]][i];
    return res;
}

void solve()
{
    cin>>n;
    for(int i=1;i<=2*n;i++) a[i]=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=2*n;i++)
        for(int j=1;j<=2*n;j++) w[i][j]=-inf;
    for(int i=1;i<=n*2;i++)
    {
        for(int j=1;j<=n*2;j++)
        {
            if(i<=n)
                w[i][j]=(-1)*abs(a[i]-j);
            else w[i][j]=0;
        }
    }
    n*=2;
    cout<<-KM()<<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

dp算法:
dp[i][j]表示第i道菜在第j分钟被拿出所需要的最小花费。

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=405;
const int inf=1e18;
const int mod=998244353;
int n,a[N],dp[N][N];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) for(int j=0;j<=n*2;j++) dp[i][j]=inf;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n*2;j++)
        {
            dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+abs(j-a[i]));
            //cout<
        }
    int ans=inf;
    for(int i=1;i<=2*n;i++) ans=min(dp[n][i],ans);
    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

C. Even Number Addicts

思路：分清必胜态、必败态、先后手影响、各自的最优策略。
1.A想让自己的总和为偶数，偶数不会影响奇偶性，但奇数可以。
2.讨论奇数的数目，及相应偶数数量可能会产生的影响。

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=405;
const int inf=1e18;
const int mod=998244353;
int n,odd,even;

void solve()
{
    odd=even=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        if(x%2) odd++;
        else even++;
    }
    if(odd%4==0) 
        cout<<"Alice"<<endl;
    else if(odd%4==1)
    {
        if(even%2) cout<<"Alice"<<endl;
        else cout<<"Bob"<<endl;
    }
    else if(odd%4==2) 
        cout<<"Bob"<<endl;
    else if(odd%4==3)
    {
        cout<<"Alice"<<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

I. Invoker

思路：明显想到要充分利用前一个指令的三个字母，才用dp记录的方式。
相当于只能储存3个字母，可打表记录。
设计状态:dp[i][j]表示字母i对应命令的第j种排列方式。
初始化：第一个字母固定需要三个命令字符
状态转移:dp[i][j]=min(dp[i][j],dp[i-1][g]+dis(mp[a[s[i-1]]][g],mp[a[s[i]]][j]));

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=405;
const int inf=1e18;
const int mod=998244353;
int n,dp[100005][6]; //第i个字母对应第j种排序方式的最小字符数
string s;
string mp[10][6]=
        {
            {"QQQ","QQQ","QQQ","QQQ","QQQ","QQQ"},
            {"QQW","QWQ","QQW","QWQ","WQQ","WQQ"},
            {"QQE","QEQ","QQE","QEQ","EQQ","EQQ"},
            {"WWW","WWW","WWW","WWW","WWW","WWW"},
            {"QWW","QWW","WQW","WWQ","WQW","WWQ"},
            {"WWE","WEW","WWE","WEW","EWW","EWW"},
            {"EEE","EEE","EEE","EEE","EEE","EEE"},
            {"QEE","QEE","EQE","EEQ","EQE","EEQ"},
            {"WEE","WEE","EWE","EEW","EWE","EEW"},
            {"QWE","QEW","WQE","WEQ","EQW","EWQ"}
        };
map<char,int>a;
int dis(string s1,string s2)
{
    if(s1==s2) return 0;
    if(s1[1]==s2[0]&&s1[2]==s2[1]) return 1;
    else if(s1[2]==s2[0]) return 2;
    else return 3;
}
void solve()
{
    a['Y']=0,a['V']=1,a['G']=2,a['C']=3,a['X']=4;
    a['Z']=5,a['T']=6,a['F']=7,a['D']=8,a['B']=9;
    cin>>s;n=s.length();s=" "+s;
    for(int i=0;i<=n;i++) for(int j=0;j<6;j++) dp[i][j]=inf;
    for(int i=0;i<6;i++) dp[1][i]=3;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<6;j++)
        {
            for(int g=0;g<6;g++)
            {
                dp[i][j]=min(dp[i][j],dp[i-1][g]+dis(mp[a[s[i-1]]][g],mp[a[s[i]]][j]));
            }
        }
    }
    int ans=inf;
    for(int i=0;i<6;i++) ans=min(ans,dp[n][i]);
    cout<<ans+n<<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