ECNA 2013 部分题解 | 训练记录

目录

• ​​提交链接​​
• ​​B . Cuckoo for Hashing [递归]​​
• ​​C . Playing Fair with Cryptography​​
• ​​F . Super Phyllis​​
• ​​H . The Urge to Merge​​
• ​​I . Xenospeak [规律模拟]​​
• ​​E . Stampede! [二分 + 网络最大流(拆点)]​​

提交链接

​

​https://codeforces.com/gym/100291/submit​

​

B . Cuckoo for Hashing [递归]

int n1, n2, m;
int a1[maxn], a2[maxn];
void modify(int f,int val) {
    if(f == 0) {
        if(a1[val % n1] == -1) a1[val % n1] = val;
        else {
            int pre = a1[val % n1];
            a1[val % n1] = val;
            modify(1,pre);
        }
    } else {
        if(a2[val % n2] == -1) a2[val % n2] = val;
        else {
            int pre = a2[val % n2];
            a2[val % n2] = val;
            modify(0,pre);
        }
    }
}
int main() {
    int _ = 0;
    
    while (~scanf("%d%d%d", &n1, &n2, &m) && m) {
        memset(a1, -1, sizeof a1);
        memset(a2, -1, sizeof a2);
        printf("Case %d:\n", ++_);
        for (int i = 1; i <= m; i++) {
            modify(0,read);
        }
        int c1 = 0,c2 = 0;
        for(int i=0;i<max(n1,n2);i++) {
            if(a1[i] != -1) c1 ++;
            if(a2[i] != -1) c2 ++;
        }
        if(c1) {
            puts("Table 1");
            for(int i=0; i<n1; i++) {
                if(a1[i] != -1) {
                    printf("%d:%d\n",i,a1[i]);
                }
            }
        }
        if(c2) {
            puts("Table 2");
            for(int i=0; i<n2; i++) {
                if(a2[i] != -1) {
                    printf("%d:%d\n",i,a2[i]);
                }
            }
        }
    }
    return 0;
}
/**


**/      

C . Playing Fair with Cryptography

​​队友传送门​​Code

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;

char a[10][10];
int b[27];
int tx[27],ty[27];

char getNext(char ch,int &idx){
    if(idx==ch-'A') idx=(idx+1)%26;
    if(idx==9) idx++;
    ch=idx+'A';
    idx=(idx+1)%26;
    if(idx==9) idx++;
    return ch;
}

void cul(char u,char v,char &x,char &y){
    int tu=u-'A',tv=v-'A';
    if(tx[tu]==tx[tv]){
        //cout<<"1"<<endl;
        //cout<<tu<<" "<<tx[tu]<<" "<<ty[tu]<<endl;
        //cout<<tv<<" "<<tx[tv]<<" "<<ty[tv]<<endl;
        //cout<<(ty[tu]+1)%5<<"***"<<(ty[tv]+1)%5<<endl;
        x=a[tx[tu]][(ty[tu]+1)%5];
        y=a[tx[tv]][(ty[tv]+1)%5];
        //cout<<x<<" "<<y<<endl;
    }else if(ty[tu]==ty[tv]){
        //cout<<"2"<<endl;
        x=a[(tx[tu]+1)%5][ty[tu]];
        y=a[(tx[tv]+1)%5][ty[tv]];
    }else{
        //cout<<"3"<<endl;
        x=a[tx[tu]][ty[tv]];
        y=a[tx[tv]][ty[tu]];
    }
}

int main(){
    int _,Case=1;cin>>_;
    while(_--){
        string ss,s="",t="",tt;
        if(Case==1) getchar();
        getline(cin,ss);
        getline(cin,tt);
    //  cout<<ss<<endl;
    //  cout<<tt<<endl;
        for(int i=0;i<ss.size();i++){
            if(ss[i]>='a'&&ss[i]<='z'){
                s+=ss[i]-'a'+'A';
            }
            else if(ss[i]>='A'&&ss[i]<='Z'){
                s+=ss[i];
            }
        }
        for(int i=0;i<tt.size();i++){
            if(tt[i]=='J') tt[i]='I';
            if(tt[i]>='a'&&tt[i]<='z') t+=tt[i]-'a'+'A';
            else if(tt[i]>='A'&&tt[i]<='Z') t+=tt[i];
        }
        //cout<<s<<endl;
        //cout<<t<<endl;
        int idx=0;
        memset(b,0,sizeof b);
        b[9]=1;
        for(int i=0;i<5;i++)
            for(int j=0;j<5;j++)
                a[i][j]='*';
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                while(b[s[idx]-'A']&&idx<s.size()) idx++;
                if(idx<s.size()){
                    a[i][j]=s[idx],b[s[idx]-'A']=1;
                }
                else break;
            }
        }
        idx=0;
        for(int i=0;i<5;i++)
            for(int j=0;j<5;j++){
                if(a[i][j]!='*') continue;
                while(b[idx]) idx++;
                a[i][j]=idx+'A';
                b[idx]=1;
            }
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                //cout<<a[i][j]<<" ";
                tx[a[i][j]-'A']=i;
                ty[a[i][j]-'A']=j;
            }
            //cout<<"\n";
        }
        idx=0;
        char x,y;
        string ans="";
        for(int i=0;i<t.size();i+=2){
            if(t[i]==t[i+1]){
                cul(t[i],getNext(t[i],idx),x,y);
                i--;
            }
            else if(i+2>t.size()){
                cul(t[i],getNext(t[i],idx),x,y);
            }
            else cul(t[i],t[i+1],x,y);
            ans=ans+x+y;
        }
        cout<<"Case "<<Case++<<": "<<ans<<endl;
    }
    return 0;
}      

F . Super Phyllis

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;

int n,a[1100][1100],Case=0,idx=0;
vector<int>g[1100]; 
map<string,int>mp;
map<int,string>mpp;
bool vis[1100];

void init(){
    idx=0;mp.clear();mpp.clear();
    memset(a,0,sizeof a);
    for(int i=0;i<1100;i++) g[i].clear();
}

int cul(string s){
    if(!mp.count(s)) mp[s]=++idx,mpp[idx]=s;
    return mp[s];
}

bool bfs(int s,int t){
    queue<int>q;
    memset(vis,0,sizeof vis);
    vis[s]=1;q.push(s);
    while(!q.empty()){
        int now=q.front();q.pop();
        if(now==t) return true;
        for(int i=0;i<g[now].size();i++){
            int j=g[now][i];
            if(!a[now][j]) continue;
            if(!vis[j]){
                vis[j]=1;q.push(j);
            }
        }
    }
    return false;
}

int main(){
    while(~scanf("%d",&n)){
        if(n==0) break;
        init();
        for(int i=1;i<=n;i++){
            string su,sv;
            cin>>su>>sv;
            int u=cul(su),v=cul(sv);
            g[u].push_back(v);
            a[u][v]=1;
        }
        vector<string>ans;    
        for(int i=1;i<=idx;i++){
            for(int j=0;j<g[i].size();j++){
                int now=g[i][j];
                a[i][now]=0;
                if(!bfs(i,now))
                    a[i][now]=1;
                else
                    ans.push_back(mpp[i]+","+mpp[now]);
            }
        }
        sort(ans.begin(),ans.end());
        cout<<"Case "<<++Case<<": "<<ans.size();
        for(int i=0;i<ans.size();i++)
            cout<<" "<<ans[i];
        cout<<"\n";
    }
    return 0;
}      

H . The Urge to Merge

#include <bits/stdc++.h>

typedef long long ll;

#pragma region Debug
template<typename T>
std::istream& operator>> (std::istream& in, std::vector<T>& vt)
{
  for (auto& i : vt) in >> i;
  return in;
}
template<typename T>
std::ostream& operator<< (std::ostream& out, const std::vector<T>& vt)
{
  for (auto& i : vt) out << i << " ";
  out << std::endl;
  return out;
}
void printAll() {  }
template<typename T1, typename... T2>
void printAll(const T1& first, const T2&... second)
{
  std::cout << first;
  if (sizeof...(second)) {
    std::cout << ", ";
  }
  printAll(second...);
}
template<typename T1, typename... T2>
void print(const T1& first, const T2&... second)
{
  std::cout << "[";
  printAll(first, second...);
  std::cout << "]" << std::endl;
}
#pragma endregion

#define N (int)(5e2 + 10)

int main()
{
  int n;
  while (std::cin >> n && n) {
    static int cas = 1;
    std::vector<std::vector<int>> v(3, std::vector<int>(n)), f(n, std::vector<int>(27));


    for (auto& str : v) {
      for (auto& ch : str) {
        std::cin >> ch;
      }
    }

    /*
    f[i][j] : 1 - i 列所有的数据，最后一列状态为j的最大值
    f[i][j] = max(f[i - 1][k] + val(j))
    */

    auto judge = [](const std::vector<int>& tmp) {
      for (int i = 0; i < tmp.size() - 1; i++) {
        if (tmp[i] == 1) {
          if (tmp[i + 1] != 1) {
            return false;
          }
          i += 1;
        }
      }
      return true;
    };

    std::vector<std::vector<int>> allSta;
    std::vector<int> allNum;
    for (int i = 0; i < 27; i++) {
      std::vector<int> tmp;
      int num = i;
      while (num) {
        tmp.push_back(num % 3);
        num /= 3;
      }
      while (tmp.size() != 3) tmp.push_back(0);

      std::reverse(tmp.begin(), tmp.end());

      if (judge(tmp)) {
        allSta.push_back(tmp);
        allNum.push_back(i);
      }
    }

    auto calc1 = [&](const std::vector<int>& sta, int col)
    {
      int res = 0;
      for (int i = 0; i < sta.size() - 1; i++) {
        if (sta[i] == 1) {
          res += v[i][col] * v[i + 1][col];
          i += 1;
        }
      }
      return res;
    };

    //print(calc1({ 0,1,1 }, 0));

    for (auto& tmp : allSta) {
      //print(tmp[0], tmp[1], tmp[2]);
    }

    const int& si = allNum.size();
    for (int i = 0; i <= 0; i++) {
      for (int j = 0; j < si; j++) {
        auto& sta = allSta[j];
        auto& num = allNum[j];

        f[i][num] = calc1(sta, i);
      }
    }

    auto judge2 = [](const std::vector<int>& curSta, const std::vector<int>& preSta) {
      for (int i = 0; i < curSta.size(); i++) {
        if (curSta[i] == 2) {
          if (preSta[i] == 1) {
            return false;
          }
          if (preSta[i] == 2) {
            return false;
          }
        }
      }
      return true;
    };

    auto calc2 = [&](const std::vector<int>& curSta, const std::vector<int>& preSta, int col)
    {
      int res = 0;
      for (int i = 0; i < curSta.size() - 1; i++) {
        if (curSta[i] == 1) {
          res += v[i][col] * v[i + 1][col];
          i += 1;
        }
        else if (curSta[i] == 2) {
          res += v[i][col] * v[i][col - 1];
        }
      }
      if (curSta[curSta.size() - 1] == 2) {
        res += v[curSta.size() - 1][col] * v[curSta.size() - 1][col - 1];
      }
      return res;
    };

    /*
    0 : 先不合并
    1 : 上下合并
    2 : 突出
    */

    int mx = 0;
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < si; j++) {
        auto& curSta = allSta[j];
        auto& curNum = allNum[j];

        for (int k = 0; k < si; k++) {
          auto& preSta = allSta[k];
          auto& preNum = allNum[k];

          if (judge2(curSta, preSta)) {
            f[i][curNum] = std::max(f[i][curNum], f[i - 1][preNum] + calc2(curSta, preSta, i));
          }
        }
        if (i == n - 1) {
          mx = std::max(mx, f[i][curNum]);
        }
      }
    }

    printf("Case %d: %d\n", cas++, mx);
    //std::cout << f[0][4] << std::endl;
  }
  return 0;
}      

I . Xenospeak [规律模拟]

ll num[1007];
string get(ll a) {
    int len = 1;
    while (num[len] < a) a -= num[len],len++;
    string s;
    s.clear();
    int fa   = 0;
    for (int i = len; i >= 1; i--) {
        ll need = num[i-1];/// 看两位，注意没有两位的情况，比如当前i为1
        if(i > 1) need += num[i-2];
        if(need >= a) s.push_back('a'),fa = 1;
        else {
            if(fa == 0) {
                s.push_back('b');
                s.push_back('b');
                a -= need;
                -- i;/// 加了两个需要再减去一个长度
            }else {
                s.push_back('b');
                a -= need;
            }
        }
    }
    return s;
}
int main() {
    num[0] = num[1] = 1;
    for (int i = 2; i <= 1000; i++) num[i] = num[i - 1] + num[i - 2] + num[i - 2];
    ll n, m;
    int _ = 0;
    while (cin >> n >> m && (n || m)) {
        printf("Case %d: %s %s\n", ++_, get(n * (m - 1) + 1).c_str(), get(n * m).c_str());
    }
    return 0;
}
/**


**/      

E . Stampede! [二分 + 网络最大流(拆点)]

/*** keep hungry and calm PushyTao!***/
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll inf   = 9223372036854775807;
const ll INF   = 0x3f3f3f3f;
const int maxn = 1e6 + 7000;

struct Edge {
    int u, v;
    ll cap, flow;
    Edge(int _u, int _v, ll _cap, ll _flow) {
        u = _u, v = _v;
        cap = _cap, flow = _flow;
    }
};
struct Dinic {
    vector<Edge> edge;
    vector<int> G[maxn << 1];
    ll dis[maxn << 1], cur[maxn << 1];
    int n, s, t;
    bool vis[maxn << 1];
    void init(int x, int _s, int _t) {
        n = x;
        for (int i = 0; i <= n; i++) G[i].clear();
        s = _s, t = _t;
        edge.clear();
    }
    void add(int u, int v, ll cap) {
        edge.push_back(Edge(u, v, cap, 0));
        edge.push_back(Edge(v, u, 0, 0));
        G[u].push_back(edge.size() - 2);
        G[v].push_back(edge.size() - 1);
    }
    bool bfs(int s, int t) {
        queue<int> que;
        memset(vis, 0, sizeof vis);
        // memset(dis,0,sizeof dis);
        dis[s] = 0;
        que.push(s);
        vis[s] = 1;
        while (que.size()) {
            int u = que.front();
            que.pop();
            for (int i = 0; i < (int)G[u].size(); i++) {
                int id = G[u][i];
                int to = edge[id].v;
                if (!vis[to] && edge[id].cap > edge[id].flow) {
                    dis[to] = dis[u] + 1;
                    que.push(to);
                    vis[to] = 1;
                }
            }
        }
        return vis[t];
    }
    ll dfs(int s, int t, ll rest) {
        if (s == t || rest == 0) return rest;
        ll Flow = 0, f;
        for (ll &i = cur[s]; i < G[s].size(); i++) {
            Edge &e = edge[G[s][i]];
            if (dis[s] + 1 == dis[e.v] && (f = dfs(e.v, t, min(rest, e.cap - e.flow))) > 0) {
                e.flow += f;
                edge[G[s][i] ^ 1].flow -= f;
                Flow += f;
                rest -= f;
                if (rest == 0) break;
            }
        }
        return Flow;
    }
    ll getMaxFlow(int s, int t) {
        ll ans = 0;
        while (bfs(s, t)) {
            memset(cur, 0, sizeof cur);
            ans += dfs(s, t, 0x3f3f3f3f);
        }
        return ans;
    }
} solve;
int n;
string s[maxn];
int getId(int x, int y, int f) {
    return x * n + y + 1 + f * n * n;
}
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
bool in(int x, int y) {
    if (x >= 0 && x <= n - 1 && y >= 0 && y <= n - 1 && s[x][y] == '.') return true;
    return false;
}
bool check(int v) {
    int st = 0, ed = n * n * (v + 1) + 1;
    solve.init(1000001, st, ed);
    for (int i = 0; i < n; i++) {
        solve.add(st, getId(i, 0, 0), 1);
        solve.add(getId(i, n - 1, v), ed, 1);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '.') {
                for (int k = 0; k < v; k++) {
                    solve.add(getId(i, j, k), getId(i, j, k + 1), 1);
                    for (int t = 0; t < 4; t++) {
                        int tox = i + dx[t];
                        int toy = j + dy[t];
                        if (in(tox, toy)) {
                            solve.add(getId(i, j, k), getId(tox, toy, k + 1), 1);
                        }
                    }
                }
            }
        }
    }
    return solve.getMaxFlow(st, ed) == n;
}
int main() {
    int _ = 0;
    while (cin >> n && n) {
        for (int i = 0; i < n; i++) cin >> s[i];
        int l = 0, r = n * n + 10;
        int ans = 0;
        while (l < r) {
            int mid = ((l + r) >> 1);
            if (check(mid)) ans = mid, r = mid;
            else l = mid + 1;
        }
        printf("Case %d: %d\n", ++_, ans);
    }
    return 0;
}