CodeForces 754C Vladik and chat (DP+暴力)

时间：2021-09-26 10:38:19

题意：给定n个人的m个对话，问能不能找一个方式使得满足，上下楼层人名不同，并且自己不提及自己。

析：首先预处理每一层能有多少个user可选，dp[i][j] 表示第 i 层是不是可以选第 j 个user。最后再输出即可。

代码如下：

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

#include <cctype>

#include <cmath>

#include <stack>

#include <sstream>

#include <unordered_map>

#include <unordered_set>

#define debug() puts("++++");

#define freopenr freopen("in.txt", "r", stdin)

#define freopenw freopen("out.txt", "w", stdout)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const LL LNF = 1LL << 60;

const double inf = 0x3f3f3f3f3f3f;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int maxn = 100 + 5;

const int mod = 2000;

const int dr[] = {-1, 1, 0, 0};

const int dc[] = {0, 0, 1, -1};

const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

int n, m;

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

inline bool is_in(int r, int c){

    return r >= 0 && r < n && c >= 0 && c < m;

}

map<string, int> mp;

int cnt;

vector<string> v;

bool vis[maxn][maxn];

int dp[maxn][maxn], a[maxn];

string name[maxn];

inline int getId(const string &s){

    if(!mp.count(s))  name[mp[s] = cnt++] = s;

    return mp[s];

}

string getF(const string &t){

    string s = "";

    for(int j = 0; t[j] != ':'; ++j)  s.push_back(t[j]);

    return s;

}

void calc1(bool *is, string s){

    for(int i = 0; i < s.size(); ++i)

        if(ispunct(s[i]))  s[i] = ' ';

   // cout << s << endl;

    stringstream ss(s);

    while(ss >> s) if(mp.count(s))  is[mp[s]] = true;

}

int main(){

    ios::sync_with_stdio(false);

    int T;  cin >> T;

    while(T--){

        cin >> n;

        mp.clear();

        cnt = 1;

        string s;

        memset(vis, 0, sizeof vis);

        for(int i = 0; i < n; ++i){

            cin >> s;

            getId(s);

        }

        cin >> m;

        cin.get();

        v.clear();

        v.push_back(" ");

        for(int i = 1; i <= m; ++i){

            getline(cin, s);

            v.push_back(s);

            calc1(vis[i], s);

            a[i] = v[i][0] == '?' ? 0 : mp[getF(s)];

        }

        memset(dp, 0, sizeof dp);

        int tmp = 1;

        dp[0][0] = 1;

        for(int i = 1; i <= m; ++i){

            int tt = 0;

            if(a[i]){

                dp[i][a[i]] = tmp > dp[i-1][a[i]];

                tt = dp[i][a[i]];

            }

            else for(int j = 1; j <= n; ++j){

                dp[i][j] = (!vis[i][j] && tmp > dp[i-1][j]);

                tt += dp[i][j];

            }

            tmp = tt;

        }

        tmp = 0;

        for(int i = 1; i <= n; ++i)  if(dp[m][i]){ tmp = i;  break;  }

        if(!tmp)  cout << "Impossible" << endl;

        else{

            for(int i = m; i > 0; --i)

                for(int j = 0; j <= n; ++j)

                    if(j != tmp && dp[i-1][j]){

                        if(!a[i])  a[i] = -tmp;

                        tmp = j;

                        break;

                    }

            for(int i = 1; i <= m; ++i)

                if(a[i] > 0)  cout << v[i] << endl;

                else cout << name[-a[i]] + v[i].substr(1) << endl;

        }

    }

    return 0;

}

相关文章