本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-10 19:07:20

题目传送门

思路

一道明显的贪心题。

我们不难发现，如果 $a_i \le a_{i-1}$ 并且 $a_i \le a_{i+1}$，那么删去 $a_i$ 是最优的。

若删去 $a_i$，则我们得到的分值为 $\min( a_{i-1}, a_{i+1} )$，比 $a_i$ 大。若不删去 $a_i$，则得到的分值最大为 $a_i$。说明在 $a_i \le a_{i-1}$ 并且 $a_i \le a_{i+1}$ 的情况下，删去 $a_i$ 是最优的。

显然，剩下的序列分为三种情况：单调上升，单调下降或者是倒 V 型。

不难发现，无论如何删，序列的最大值和次大值的分数不可能取到。

若能取到最大值的分数，则必定有两个数比最大值大，不符实际。次大值同理。

所以，我们将答案还要加上 $\sum\limits_{i = 1}^{n-2} a_i$。（$a$ 序列为删完的序列）

我们可以用栈来实现。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
#define int long long
const int N=5e5+55;
int a[N],vis[N];
int tot,res;
stack<int> st;
signed main(){
    int n;
    cin>>n;
    
    for(int i=1;i<=n;i++){
        int d;
        cin>>d;
        while(st.size()>=2){
            int x=st.top();\/\/栈顶
            st.pop();
            int y=st.top();\/\/栈的第二个
            if(x<=y&&x<=d){\/\/这里是<=而不是<!!!!
                res+=min(y,d);
            }
            else{
                st.push(x);
                break;
            }
        }
        st.push(d);
    }
    while(!st.empty()){
        tot++;
        a[tot]=st.top();
        st.pop();
    }
    sort(a+1,a+tot+1);
    for(int i=1;i<=tot-2;i++) res+=a[i];
    cout<<res<<endl;
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-16 19:45:14

A

不会，不写了。

B

是个好题。

20分暴力，40分容斥+子集枚举（挺简单的），100分容斥+动归。

我们发现，

设 $f_{i,j}$ 为表示 $[1, i]$ 不被 $a$ 数组中的元素整除的数有多少个。

初始化 $f_{i,0}=i$ 。

我们可以很简单的推出状态转移方程

$$f_{i,j}=f_{i,j-1}-f_{i÷a_j , j-1} $$

但是我们发现，数据范围不可取，$n<=10^{13}$，数组炸了。

但是我们可以用记忆化搜索，这正是这道题的精妙之处。

当 $n<=10000$ 时，我们可以用动规，否则，我们可以用记忆化搜索做，时间复杂度刚好不炸。

（听说将数组sort之后速度会提升许多，不知道为什么）

C

线段树。

有三种方式合并

1111111 ---- 111111111

000000------- 000000

111111 ---- 000000

求最长01串。

思路会，只可惜不会打，暴力20分。

D

傻逼题。

直接出结论

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-17 14:37:37

纯纯大模拟+DFS+贪心。

这个题要注意的细节挺多的（交了10发，一上午才过）。

打过扑克的都知道，顺子一次能出最多的牌，三带一四带二其次，对子炸弹和单牌在最后。 我们可以以此来进行贪心。

我们先判断顺子，分为三种情况：单，双，三。

我们可以从3开始，一直查到A，

然后是带（三带一之类的），我们先找到三张以上的牌，再继续从3查到大小王，只要有一张就可以深搜。但是注意，三 和 带一 的点不能相同，不然就是炸弹了。（3张5不能带上1张5，这种情况后面判断）。

注意：四带二分为两种情况，带两张单牌和两张对子。

在最后，我们不难发现，剩下的牌每一种点都能一次出去，所以只需要统计有多少种点就是还要几步。

细节：

• 这里我们用桶来存牌的点，从3到K都正常存，A存 $t_{14}$,2存 $t_{15}$，大小王存 $t_{16}$，$t_1$ 和 $t_2$ 不存。

• x循环遍历时，i,j,k三个变量及其容易弄混，本人就因为这找了大半个上午。

• 整个DFS都别忘了回溯。

代码赠详细解析

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int N=20;
long long n,k;
int t[N];
int minn;
void dfs(int x){\/\/别忘了回溯
    if(x>=minn) return ;\/\/剪枝优化
    int k=0;\/\/单顺子的长度
    for(int i=3;i<=14;i++){
        if(t[i]==0) k=0;
        else{
            k++;
            if(k>=5){
                for(int j=i-k+1;j<=i;j++) t[j]--;
                dfs(x+1);
                for(int j=i-k+1;j<=i;j++) t[j]++;\/\/回溯
            }
        }
    }
    k=0;\/\/双顺子的长度
    for(int i=3;i<=14;i++){
        if(t[i]<=1) k=0;
        else{
            k++;
            if(k>=3){
                for(int j=i-k+1;j<=i;j++) t[j]-=2;
                dfs(x+1);
                for(int j=i-k+1;j<=i;j++) t[j]+=2;
            }
        }
    }
    k=0;\/\/3顺子的长度
    for(int i=3;i<=14;i++){
        if(t[i]<=2) k=0;
        else{
            k++;
            if(k>=2){
                for(int j=i-k+1;j<=i;j++) t[j]-=3;
                dfs(x+1);
                for(int j=i-k+1;j<=i;j++) t[j]+=3;
            }
        }
    }
    for(int i=3;i<=15;i++){
        if(t[i]>=3){
            t[i]-=3;
            for(int j=3;j<=16;j++){\/\/三带一
                if(t[j]>0&&i!=j){\/\/若i==j就等于炸弹
                    t[j]--;
                    dfs(x+1);
                    t[j]++;
                }
            }
            for(int j=3;j<=15;j++){\/\/三代二（王炸不是对牌）
                if(t[j]>=2&&i!=j){
                    t[j]-=2;
                    dfs(x+1);
                    t[j]+=2;
                }
            }
            t[i]+=3;
        }
        if(t[i]>=4){
            t[i]-=4;
            for(int j=3;j<=16;j++){\/\/4+2(单)
                if(t[j]>=1&&i!=j){
                    t[j]--;
                    for(int k=3;k<=16;k++){
                        if(t[k]>=1&&j!=k){
                            t[k]--;
                            dfs(x+1);
                            t[k]++;
                        }
                    }
                    t[j]++;
                }
            }
            for(int j=3;j<=15;j++){\/\/4+2（对子）
                if(t[j]>=2&&i!=j){
                    t[j]-=2;
                    for(int k=3;k<=15;k++){
                        if(t[k]>=2&&j!=k){
                            t[k]-=2;
                            dfs(x+1);
                            t[k]+=2;
                        }
                    }
                    t[j]+=2;
                }
            }
            t[i]+=4;
        }
    }
    for(int i=3;i<=16;i++){
        if(t[i]>0){
            x++;
        }
    }
    minn=min(minn,x);
}
signed main() {
    int T,n;
    cin>>T>>n;
    while(T--){
        memset(t,0,sizeof(t));
        minn=0x3f3f3f3f;
        for(int i=1;i<=n;i++){
            int x,y;
            cin>>x>>y;
            if(x==0) t[16]++;\/\/大小王
            else if(x==2) t[15]++;\/\/2
            else if(x==1) t[14]++;\/\/A
            else t[x]++;
        }
        dfs(0);
        cout<<minn<<endl;
    }

    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-17 19:36:18

题面

对于两个长度为 $n$ 的 $01$ 串 $s,t$ ，你可以对 $s$ 进行两种操作：把相邻两个 $0$ 变成 $1$ 或把相邻两个 $1$ 变成 $0$ ，定义 $s$ 到 $t$ 的距离为最少操作次数使得 $s$ 变成 $t$ ，如过没法变则距离为 $0$ 。

现在你有两个不完整的字符串，可以把其中的 $?$ 变成 $0$ 或 $1$ ，求所有情况所得到的两个 $01$ 串的距离之和。

思路

我们发现，直接按照题意操作是非常复杂且不雅的。有一个十分新奇的思路（难绷）：将s和t的奇数位取反。

设 $s=100111011000$，$t=111100011011$，则最少操作步数为3次，（2,3/5,6/11,12)，我们将奇数位取反后发现，$s'=001101110010$，$t'=010110110001$。此时，我们便发现，原问题转化为有两01串，我们可以将 $01$ 转成 $10$ 或将 $10$ 转成 $01$ 使两字符串相同所需要的最小步数。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-19 20:28:21

题意

将长度为 $n$ 的序列分成 $k$ 段，使得总价值最大。

一段区间内的价值为区间内不同数字的个数。

思路

一眼DP。
定义 $dp_{i,j}$ 为将 $1-j$ 分为 $i$ 段的最大价值，$w(i,j)$ 为从 $i$ 到 $j$ 的价值，不难列出转移方程：

$$dp_{i,j}=max(dp_{i-1,k}+w(k+1,j))$$

看起来不错，可惜时空复杂度均超。$O (n^3k)$ 什么玩意。

我们注意到，每种颜色 $i$ 有贡献的区间为上一个颜色 $i$ 出现的位置 加一 到该颜色的下标。

(非常形象的图）

结合上图，可以发现，每一个颜色区间的价值都要加一，而我们查询也是区间查询，明显线段树优化DP。

我们每次枚举切割次数时，都将线段树清空并重新建树。

这里我们注意，线段树的建树是要继承上一次DP的值，所以 tr[rt].sum=f[now-1][l-1];。

于是乎，时间复杂度成功降为 $O(n·k \log n)$。

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std;

#define ll long long

const int N=35005;\/\/注意修改
const int mod=1e9+7;

int a[N];
int f[55][N];
int co[5005][5005],t[N],lst[N],xy[N];

struct tree{
    int l,r;
    int add;\/\/懒标记
    int sum;
}tr[N<<2];

void pushup(int rt){
    tr[rt].sum=max(tr[rt<<1].sum,tr[rt<<1|1].sum);
}

void build(int rt,int l,int r,int now){
    tr[rt].l=l;
    tr[rt].r=r;
    if(l==r){
        tr[rt].sum=f[now-1][l-1];\/\/这里与动归数组一样。
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid,now);
    build(rt<<1|1,mid+1,r,now);
    pushup(rt);
}

void pushdown(int rt){
    if(tr[rt].add==0) return;
    tr[rt<<1].add+=tr[rt].add;
    tr[rt<<1].sum+=tr[rt].add;
    tr[rt<<1|1].add+=tr[rt].add;
    tr[rt<<1|1].sum+=tr[rt].add;
    tr[rt].add=0;
}

void add(int rt,int l,int r,int k){
    if(tr[rt].l>=l&&tr[rt].r<=r){
        tr[rt].add+=k;
        tr[rt].sum+=k;
        return ;
    }
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;\/\/cao
    if(l>mid) add(rt<<1|1,l,r,k);
    else if(r<=mid){
        add(rt<<1,l,r,k);
    }
    else{
        add(rt<<1,l,mid,k);
        add(rt<<1|1,mid+1,r,k);
    }
    pushup(rt);
}

int query(int rt,int l,int r){\/\/这里查询的是最大值，而不是和！
    if(tr[rt].l==l&&tr[rt].r==r){
        return tr[rt].sum;
    }
    if(tr[rt].l==tr[rt].r) return 0;
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;
    
    if(l>mid) return query(rt<<1|1,l,r);
    else if(r<=mid){
        return query(rt<<1,l,r);
    }
    else{
        return max(query(rt<<1,l,mid),query(rt<<1|1,mid+1,r));
    }
    
}
int main(){
\/\/    freopen(".in","r",stdin);
\/\/    freopen(".out","w",stdout);
    
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        lst[i]=xy[a[i]]+1;\/\/上一个此颜色的位置
        xy[a[i]]=i;
    }
    for(int i=1;i<=m;i++){
        memset(tr,0,sizeof(tr));\/\/
        build(1,1,n,i);
        for(int j=1;j<=n;j++){
            add(1,lst[j],j,1);
            f[i][j]=query(1,1,j);
            
        }
    }
    cout<<f[m][n];
    return 0;
    
\/\/    fclose(stdin);
\/\/    fclose(stdout);
}

\/*


 *\/

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-22 19:16:29

概念

二分图是图论中的一个重要概念，指的是一个图的顶点集可以被分为两个互不相交的子集，并且图中的每条边都连接两个不同子集中的顶点。换句话说，如果一个图是二分图，那么可以将图中的所有顶点分为两组，使得每条边的两个端点分别属于不同的组。

二分图 当且仅当 图中不含奇数环。

判断

染色法

1.选择一个起始顶点，将其染成一种颜色（比如红色）。

2.将与该顶点相邻的顶点染成另一种颜色（比如蓝色）。

3.依次对与 已染色的顶点 相邻的未染色顶点进行染色，要求相邻顶点的颜色不能相同。

4.如果在染色的过程中，发现有相邻的两个顶点被染成了相同的颜色，则说明该图不能划分成二分图；否则，当所有顶点都被染色后，该图可以划分成二分图。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-23 13:27:51

类似区间取模，我们发现即使极差极大的序列，在经过几次开方之后便可以趋近于相等，最后序列中的元素都变成 $1$。

我们不难发现，当序列中的数都相等时，将序列开方，发现序列里的数均相同。换句话说，将序列开方，序列里的数均减去一个 $x$。

当序列极差为 $1$ 时，将其开方会有两种情况：

1.开完方之后序列极差为0，下次开根就是区间减法。

2.开完方之后极差为1，开根相当于均减1个数。

若极差大于1，则暴力开根。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>

using namespace std;

#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


const int N=1e5+5;\/\/注意修改
const int mod=1e9+7;
int a[N];
struct tree{
    int l,r;
    int sum;
    int add;
    int mx,mn;
}tr[N<<2];
void pushup(int rt){
    tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
    tr[rt].mx=max(tr[rt<<1].mx,tr[rt<<1|1].mx);
    tr[rt].mn=min(tr[rt<<1].mn,tr[rt<<1|1].mn);
}
void pushdown(int rt){
    if(tr[rt].add==0) return ;
    tr[rt<<1].add+=tr[rt].add;
    tr[rt<<1].sum+=tr[rt].add*(tr[rt<<1].r-tr[rt<<1].l+1);
    tr[rt<<1|1].add+=tr[rt].add;
    tr[rt<<1|1].sum+=tr[rt].add*(tr[rt<<1|1].r-tr[rt<<1|1].l+1);
    tr[rt<<1].mx+=tr[rt].add;
    tr[rt<<1].mn+=tr[rt].add;
    tr[rt<<1|1].mx+=tr[rt].add;
    tr[rt<<1|1].mn+=tr[rt].add;
    tr[rt].add=0;
}
void build(int rt,int l,int r){
    tr[rt].l=l;
    tr[rt].r=r;
    tr[rt].add=0;
    if(l==r){
        tr[rt].sum=a[l];
        tr[rt].mx=a[l];
        tr[rt].mn=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}
void sub(int rt,int l,int r,int x){
    tr[rt].add-=x;
    tr[rt].mx-=x;
    tr[rt].mn-=x;
    tr[rt].sum-=x*(r-l+1);
}
void add(int rt,int l,int r,int k){
    \/\/cout<<rt<<" "<<l<<" "<<r<<endl;
    if(tr[rt].l>=l&&tr[rt].r<=r){
        tr[rt].add+=k;
        tr[rt].sum+=k*(tr[rt].r-tr[rt].l+1);
        tr[rt].mx+=k;
        tr[rt].mn+=k;
        return ;
    }
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;
    if(l<=mid) add(rt<<1,l,r,k);
    if(r>mid) add(rt<<1|1,l,r,k);
    pushup(rt);
}
int query(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r){
        return tr[rt].sum;
    }
    if(tr[rt].l==tr[rt].r) return 0;
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;
    int res=0;
    if(l<=mid) res+=query(rt<<1,l,r);
    if(r>mid) res+=query(rt<<1|1,l,r);
    pushup(rt);
    return res;
}
void Sqrt(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r){
        int Max=tr[rt].mx;
        int Min=tr[rt].mn;
        if(Max-Min<=1&&(int)sqrt(Max)-(int)sqrt(Min)==Max-Min){
            sub(rt,tr[rt].l,tr[rt].r,Max-(int)sqrt(Max));
            return ;
        }
    }
    pushdown(rt);
    int mid=(tr[rt].l+tr[rt].r)>>1;
    if(l<=mid) Sqrt(rt<<1,l,r);
    if(r>mid) Sqrt(rt<<1|1,l,r);
    pushup(rt);
}
signed main(){
    fst
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
\/\/    for(int i=1;i<=n<<2;i++){
\/\/        cout<<tr[i].sum<<" ";
\/\/    }
\/\/    cout<<endl;
    for(int i=1;i<=m;i++){
        int op,x,y;
        cin>>op;
        if(op==1){
            int k;
            cin>>x>>y>>k;
            add(1,x,y,k);
        }
        if(op==2){
            cin>>x>>y;
            Sqrt(1,x,y);
        }
        if(op==3){
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
        \/\/cout<<query(1,1,n)<<endl<<endl;
    }
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-21 16:08:25

题目描述

给定一个序列，每次操作可以把某个数加上 $1$ 或减去 $1$。要求把序列变成非降数列。最小化操作次数。

我们发现，要把一个数列改成一个非严格递增的数列，要么这个数还是自己，要么这个数就是前面一个数，不然总不是最优的，可以手动模拟看一看。

此题显然用DP。

我们设 $f_{i,j}$ 为第 $i$ 位放 $j$ 时的最小花费。

根据前面的推导，我们将 $a$ 数组从小到大排序记为 $b$ 数组，则$f_{i,j}$ 为第 $i$ 位放 $b_j$ 时的最小花费。

显然可推出状态转移方程

$$f_{i,j}=(f_{i-1,k})_{min}+|a_i-b_j|$$

其中 $k$ 从数组的最小值遍历到最大值。

我们可以再用一个数组 $mi_{i,j}$ 来计算 $min(f_{i,k})$

$$mi_{i,j}=min(mi_{i,j-1},f_{i,j})$$

状态转移方程为：

$$f_{i,j}=mi_{i-1,j}+|a_i-b_j|$$

提交之后就MLE了。

我们发现，$f$ 只和 $f_{i-1}$ 和 $f_i$ 有关系，所以我们可以用滚动数组优化DP。

$f_{i-1}$ 为 $f_0$，$f_i$ 为 $f_1$。

则最终的状态转移方程为：

$$f_{1,j}=min(f_{1,j-1},f_{0,j}+|a_i-b_j|)$$

注：此时可以将 $mi$ 数组和 $f$ 数组合并，原本的状态转移方程为：

$$mi_{1,j}=min(mi_{1,j-1},ff)$$

$$ff=mi_{0,j}+|a_i-b_j|$$

所以就AC了

代码

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int N=5005;
int a[N];
int f[2][N];
int b[N];
int n,m;
signed main(){
    int  n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){
        f[1][0]=1e18;
        for(int j=1;j<=n;j++){
            f[1][j]=min(f[1][j-1],f[0][j]+abs(a[i]-b[j]));
        }
        for(int j=1;j<=n;j++) f[0][j]=f[1][j];
        
    }
    cout<<f[1][n];
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-21 16:13:17

第一道紫题

题面翻译

给定一个有 $n$ 个正整数的数组，一次操作中，可以把任意一个元素加一或减一。（元素可被减至负数或 $0$），求使得原序列严格递增的求最小操作次数。

样例

样例输入

7
2 1 5 11 5 9 11

样例输出

9

可将样例序列变为 $2$ $3$ $5$ $6$ $7$ $9$ $11$。

这道题和CF13C有异曲同工之妙。

只不过 CF13C 是非严格递增（序列之间的数可以相等），此题是严格递增（必须小于）。

先看这篇题解 。

我的题解（CF13C）

我们现在只需要想如何让数列成为严格递增。

我们可以让 $a_i - i$，即使$a_i - i$ 与 $a_{i-1} - (i-1)$ 相等，展开为

$$ a_i=a_{i-1}-i+i+1$$

$$ a_i=a_{i-1}+1$$

这样就是一个严格递增的数列了。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=50005;
int a[N];
int f[2][N];
int b[N];
int n,m;
signed main(){
    int  n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        b[i]=a[i]=a[i]-i;\/\/只改了这里
    }
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){
        f[1][0]=1e18;
        for(int j=1;j<=n;j++){
            f[1][j]=min(f[1][j-1],f[0][j]+abs(a[i]-b[j]));
        }
        for(int j=1;j<=n;j++) f[0][j]=f[1][j];
        
    }
    cout<<f[1][n];
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-23 16:18:28

题意

简简单单，自己看题去。

题目传送门

思路

注：不知道某变量数组干什么用时请看定义。

定义

定义一个数组 $week$,记录编号从 $1$ 到 $7$ 日期的句子。

string weeks[10]={
    "11451411",
    "Today is Monday.",
    "Today is Tuesday.",
    "Today is Wednesday.",
    "Today is Thursday.",
    "Today is Friday.",
    "Today is Saturday.",
    "Today is Sunday."
};

定义一个 $map$ $nameid$ 存名字的编号。

定义一个结构体数组 $names$，$id$ 存名字的编号，$zh$ 存证词。

定义一个数组 $dis$ 判断第 $i$ 句话是否是真的。

若 $dis_i$ 为 $-1$，则第 $i$ 句话不确定真假。

若 $dis_i$ 为 $0$，则第 $i$ 句话是假的。

若 $dis_i$ 为 $1$，则第 $i$ 句话是真的。

定义两个变量 $tr$ 和 $fs$，分别记录真话个数和假话个数。

定义一个变量 $chiefid$ 记录凶手编号。

定义一个变量 $pos$ 记录题目中要求的5个字符串是否出现过，若 $pos$ 等于 $-1$ ，说明此字符串没有出现过，否则就是出现过（因为pos=s.find("...");)

传入 check 的一个参数 $na$，代表 main 中枚举的犯人编号。

传入 check 的一个参数 $day$, 代表 main 中枚举的日期。

传入 judge 的一个参数 $i$，代表 check 中枚举的犯人编号。

传入 judge 的一个参数 $f$, 代表 check 中，根据题意是否符合要求。

main 函数

首先我们能看出这是一道纯纯的模拟题。

这道题细节很多，有些还有坑人的地方。

我们先可以记录说话的人以及他的编号。 再记录证词。

注意 ：输入人名时，要用 erase函数 删去人名后面的冒号，输入证词时用getline，要删去开头的一个空格。

我们遍历每一个人，每一个日子（从周一到周天），将它们放入check函数中进行判断查找，并记录犯人编号。

如果犯人编号记录了，也就是犯人编号不是0，就可以输出，负责输出 Impossible。

注：要在输入完证词猴判断后面是否有换行符，（不是谁做题回想这个，还不是看题解，无语了，亲测，不加此句只得50分）

main代码

signed main(){
    cin>>m>>n>>p;
    for(int i=1;i<=m;i++){
        cin>>name[i];
        nameid[name[i]]=i;
    }
    for(int i=1;i<=p;i++){
        string na;
        cin>>na;
        na.erase(na.size()-1,1);
        \/\/cout<<na;
        \/\/char kong;
        \/\/cin>>kong;\/\/读入中间的空格
        string zh;\/\/证词
        getline(cin,zh);
        zh.erase(0,1);
        if(zh[zh.size()-1]=='\n'||zh[zh.size()-1]=='\r')
                zh.erase(zh.size()-1,1);
        \/\/cout<<zh<<endl;
        names[i].id=nameid[na];
        names[i].zh=zh;
        
    }
    \/\/cout<<endl;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=7;j++){
            check(i,j);
        }
    }
    if(chiefid==0){
        cout<<"Impossible";
        return 0;
    }
    cout<<name[chiefid]<<endl;
    return 0;
}

check 函数

将 $tr$,$fs$ 初始化为 $0$。

将 $dis$ 初始化为 $-1$。

遍历每一条证词，寻找题目要求的五句话：

1. I am guilty.

2. I am not guilty.

3. (此处为空格)is guilty.

4. (此处为空格)is not guilty.

5. Today is(此处为空格)

如果找到了，那么进入 judge 函数，判断此句是否为真。

如果 judge 为真，那么直接结束 check。

在 check 的倒数第二步，判断 $chiefid$ 是否是第二次出现（即$chiefid \ne 0$ $and$ $chiefid \ne na$ )

最后，将 $chiefid$ 赋为 $na$。

check 代码

void check(int na,int day){
    \/\/cout<<chiefid;
    tr=0;
    fs=0;
    memset(dis,-1,sizeof(dis));
    for(int i=1;i<=p;i++){
        int pos;
        pos=names[i].zh.find("I am guilty");
        if(pos!=-1){
            \/\/cout<<114514;
            bool f=names[i].id==na;
            if(judge(names[i].id,f)){
                \/\/cout<<1919810;
                
                return ;
            }
        }
        pos=names[i].zh.find("I am not guilty");
        if(pos!=-1){
            bool f=names[i].id!=na;
            if(judge(names[i].id,f)){
                
                return ;
            }
        }
        pos=names[i].zh.find(" is guilty.");
        \/\/cout<<"pos: "<<pos<<endl;
        if(pos!=-1){
            
            string nam=names[i].zh;
            nam.erase(pos,11);\/\/截掉后面的只保留前面名字
            bool f=nameid[nam]==na;
            if(judge(names[i].id,f)){
                
                return ;
            }
        }
        pos=names[i].zh.find(" is not guilty.");
        \/\/cout<<"pos: "<<pos<<endl;
        if(pos!=-1){
            string nam=names[i].zh;
            nam.erase(pos,15);\/\/同上
            bool f=nameid[nam]!=na;
            if(judge(names[i].id,f)){
                
                return ;
            }
        }
        pos=names[i].zh.find("Today is ");
        if(pos!=-1){
            bool f=names[i].zh==weeks[day];
            if(judge(names[i].id,f)){
                
                return;
            }
        }
    }
    if(chiefid!=0&&chiefid!=na){
        \/\/cout<<endl<<na<<" "<<day<<" "<<chiefid<<endl;
        cout<<"Cannot Determine";
        exit(0);
    }
    chiefid=na;
    
    return ;
}

judge 函数

分两个角度判断：

1. 若 $dis_i=-1$

   2.其他情况

情况1：将 $dis_i$ 赋值为 $f$。如果 $f$ 为真，$tr$ 加一；反之，$fs$ 加一。

情况2： 如果 $dis_i$ 等于 $f$,返回假，否则返回真。

最后判断一下真话个数和假话个数是否合法，合法返回假，否则返回真。

注：judge 返回真就是在 check 中直接return。

judge 代码

bool judge(int i,bool f){
    \/\/cout<<endl<<"T "<<tr<<"  F "<<fs<<endl<<endl;
    \/\/cout<<endl<<i<<" "<<f<<endl;
    if(dis[i]==-1){
        dis[i]=f;
        if(f){
            tr++;
        }
        else{
            fs++;
        }
    }
    else{
        if(dis[i]==f){
            return 0;
        }
        else return 1;
    }
    if(fs<=n&&tr<=m-n){
        return 0;
    }
    return 1;
}

总代码

#include<iostream>
#include<cstring>
#include<string>
#include<map>
#define int long long
using namespace std;
const int N=5005;
string weeks[10]={
    "11451411",
    "Today is Monday.",
    "Today is Tuesday.",
    "Today is Wednesday.",
    "Today is Thursday.",
    "Today is Friday.",
    "Today is Saturday.",
    "Today is Sunday."
};
int a[N];
int f[2][N];
int b[N];
int n,m,p;
int dis[N];
string name[N];
map<string,int> nameid;\/\/每个名字的下标
struct namess{
    string zh;
    int id;
}names[N];
int tr,fs;
bool judge(int i,bool f){
    \/\/cout<<endl<<"T "<<tr<<"  F "<<fs<<endl<<endl;
    \/\/cout<<endl<<i<<" "<<f<<endl;
    if(dis[i]==-1){
        dis[i]=f;
        if(f){
            tr++;
        }
        else{
            fs++;
        }
    }
    else{
        if(dis[i]==f){
            return 0;
        }
        else return 1;
    }
    if(fs<=n&&tr<=m-n){
        return 0;
    }
    return 1;
}
int chiefid;
void check(int na,int day){
    \/\/cout<<chiefid;
    tr=0;
    fs=0;
    memset(dis,-1,sizeof(dis));
    for(int i=1;i<=p;i++){
        int pos;
        pos=names[i].zh.find("I am guilty");
        if(pos!=-1){
            \/\/cout<<114514;
            bool f=names[i].id==na;
            if(judge(names[i].id,f)){
                \/\/cout<<1919810;
                
                return ;
            }
        }
        pos=names[i].zh.find("I am not guilty");
        if(pos!=-1){
            bool f=names[i].id!=na;
            if(judge(names[i].id,f)){
                
                return ;
            }
        }
        pos=names[i].zh.find(" is guilty.");
        \/\/cout<<"pos: "<<pos<<endl;
        if(pos!=-1){
            
            string nam=names[i].zh;
            nam.erase(pos,11);
            bool f=nameid[nam]==na;
            if(judge(names[i].id,f)){
                
                return ;
            }
        }
        pos=names[i].zh.find(" is not guilty.");
        \/\/cout<<"pos: "<<pos<<endl;
        if(pos!=-1){
            string nam=names[i].zh;
            nam.erase(pos,15);
            bool f=nameid[nam]!=na;
            if(judge(names[i].id,f)){
                
                return ;
            }
        }
        pos=names[i].zh.find("Today is ");
        if(pos!=-1){
            bool f=names[i].zh==weeks[day];
            if(judge(names[i].id,f)){
                
                return;
            }
        }
    }
    if(chiefid!=0&&chiefid!=na){
        \/\/cout<<endl<<na<<" "<<day<<" "<<chiefid<<endl;
        cout<<"Cannot Determine";
        exit(0);
    }
    chiefid=na;
    
    return ;
}
signed main(){
    cin>>m>>n>>p;
    for(int i=1;i<=m;i++){
        cin>>name[i];
        nameid[name[i]]=i;
    }
    for(int i=1;i<=p;i++){
        string na;
        cin>>na;
        na.erase(na.size()-1,1);
        \/\/cout<<na;
        \/\/char kong;
        \/\/cin>>kong;\/\/读入中间的空格
        string zh;\/\/证词
        getline(cin,zh);
        zh.erase(0,1);
        if(zh[zh.size()-1]=='\n'||zh[zh.size()-1]=='\r')
                zh.erase(zh.size()-1,1);
        \/\/cout<<zh<<endl;
        names[i].id=nameid[na];
        names[i].zh=zh;
        
    }
    \/\/cout<<endl;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=7;j++){
            check(i,j);
        }
    }
    if(chiefid==0){
        cout<<"Impossible";
        return 0;
    }
    cout<<name[chiefid]<<endl;
    return 0;
}

撒花完结。