傳送門

文章目錄

• 題意：
• 思路：

題意：

給你一個長度為$27$的字符串$s$，其中$26$個字母每種都至少出現一次，讓你構造一個$2\times 13$的矩陣，使得每個字母都出現一次，并且存在一條路徑，經過這個路徑上的點組成的字符串是$s$，你可與向$8$個方向走，有解輸出矩陣，無解輸出$Impossible$。

思路：

一開始看錯題了，卡了半天。

明顯，$s$串中恰好有兩個字母相同，所以當相同的兩個字母相鄰的時候，這個時候是無解的。

否則一定有解，通過畫一畫不難發現，我們可以在第一行確定一個起點，讓后向右走，走到頭之后向下，依次這樣蛇形的填滿，由于我們需要經過相同的字母兩次，所以可以設計這個字母出現在第一行，讓后從第二行跳到這個位置，再跳到原本的下一個位置即可。所以我們一定存在一種蛇形填數是符合條件的。

有了上面的結論，直接枚舉所有情況讓后檢查即可。

// Problem: F - Hidden Word // Contest: Virtual Judge - Camp4 // URL: https://vjudge.net/contest/455435#problem/F // Memory Limit: 262 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int c[30],ne[N]; char s[100]; vector<int>v[2]; PII p[N]; int dir[8][2]={1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,1,-1,-1};bool check() {int x,y;for(int i=0;i<2;i++) {for(int j=0;j<13;j++) {if(v[i][j]==s[1]-'A') {x=i; y=j;continue;}}}int cnt=1;queue<PII>q; q.push({x,y});while(cnt<27&&q.size()) {PII u=q.front(); q.pop();for(int k=0;k<8;k++) {int dx=u.X+dir[k][0];int dy=u.Y+dir[k][1];if(dx<0||dy<0||dx>=2||dy>=13) continue;if(v[dx][dy]==s[cnt+1]-'A') {q.push({dx,dy});cnt++;break;}} }if(cnt==27) return true;else return false; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);cin>>(s+1);int ch; bool flag=true;for(int i=1;i<=27;i++) {c[s[i]-'A']++;if(c[s[i]-'A']==2) {if(s[i-1]==s[i]) flag=false;}}if(!flag) {puts("Impossible");return 0;}for(int i=1;i<=27;i++) {if(c[s[i]-'A']) {if(v[0].size()<13) v[0].pb(s[i]-'A');else v[1].pb(s[i]-'A');}c[s[i]-'A']=0;}reverse(v[1].begin(),v[1].end());while(!check()) {vector<int>vv1,vv2;vv1.pb(v[1][0]);for(int i=0;i<12;i++) vv1.pb(v[0][i]);for(int i=1;i<13;i++) vv2.pb(v[1][i]);vv2.pb(v[0][12]);v[0]=vv1; v[1]=vv2;// for(auto x:v[0]) cout<<x<<' '; puts("");// for(auto x:v[1]) cout<<x<<' '; puts("");// puts("");}for(auto x:v[0]) cout<<(char)(x+'A'); puts("");for(auto x:v[1]) cout<<(char)(x+'A'); puts("");return 0; } /*ABCDEFGHIJKLM NOPQRSGTUVWXYZABCDEFGHIJKLM ZYXWVUTSRQPON*/

總結

以上是生活随笔為你收集整理的Canada Cup 2016 C. Hidden Word 字符串构造的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。