卡了好几天,总算把DAY 20的基础题写了...(对我来说还是很卡手的
(8.13 22:49正准备完结这一天的时候,突然发现挂掉的A题还没写...先去补上再来总结)
A.Gift from the Goddess of Programming Aizu 1315
一个人一天可以进去多次,模拟没啥好说的,只有我这种傻逼才会写挂
B.The Sorcerer's Donut Aizu 1316
题意:给你一个大写字母的矩阵,可以从任一点任一方向拓展(八个方向,无边界),最多拓展到起点,问重复出现过的字符串最长的是哪一个,多解输出字典序最小的,
解的长度必须大于等于2
就是一个暴力枚举+map判重
可以记录一个当前最优解的长度maxlen(重复出现过的字符串最长长度, 初始为2), 只有当枚举的字符串长度大于等于这个值, 才进行操作
如果串没出现过,map标记下,出现过的话,长度是否等于maxlen?添加当前串到解集:更新长度,解集清空,加入当前解
解集就是一个string数组,最后sort下输出ans[0]
整体看下来,代码量还是很小的,就是自己第一次写map~
#include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <map> #include <vector> #include <algorithm> using namespace std; const int maxn = 40; const int dx[] = {1, -1, 0, 0 , 1, 1, -1, -1}, dy[] = {0, 0, 1, -1, 1, -1, 1, -1}; int n, m, ml, cnt; char donut[maxn][maxn]; string ans[2000]; map<string, int> mp; int main() { #ifdef LOCAL freopen("B.in", "r", stdin); #endif while(scanf("%d%d", &n, &m) != EOF) { if(n == 0 && m == 0) break; ml = cnt = 0; mp.clear(); for(int i = 0; i < n; i++) scanf("%s", donut[i]); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int k = 0; k < 8; k++) { string tmp = ""; int nx = i, ny = j; do{ tmp += donut[nx][ny]; if(tmp.size() >= 2 && tmp.size() >= ml) { if(!mp[tmp]) mp.insert(pair <string, int> (tmp, 1)); else if(tmp.size() == ml && mp[tmp] == 1) ans[cnt++] = tmp; else if(tmp.size() > ml) { ml = tmp.size(); cnt = 0; ans[cnt++] = tmp; } } mp[tmp]++; nx = (nx+dx[k]+n)%n; ny = (ny+dy[k]+m)%m; }while(nx != i || ny != j); // cout << tmp << endl; /* if(!mp[tmp]) mp.insert(pair <string, int> (tmp, 1)); else { if(tmp.size() == ml && mp[tmp] == 1) { ans[cnt++] = tmp; } else if(tmp.size() > ml) { ml = tmp.size(); cnt = 0; ans[cnt++] = tmp; } mp[tmp]++; } */ } sort(ans, ans+cnt); if(cnt) printf("%s ", ans[0].c_str()); else printf("0 "); } return 0; }
D.Long Distance Taxi Aizu 1318
训练的时候是想出了正确解法,只是自己不敢去写,也确实写不出来....
容易想到,要么不经过加油站,要么经过,经过加油站的话,最后一定从某个加油站出发到达终点,可以重新建一个图,只包含加油站和终点起点
先对这些点都跑一遍最短路,在gas*10的距离内能达到的点,就连一条边,表示以满油状态这两个点可以互达(这里就把限制条件解决了)
再对新建的图跑一遍最短路就解决问题了...
通过传递参数,只需要写一个spfa(也是回味了下怎么写spfa....)
细节比较麻烦的是一开始的建图,可以用map来标记已经读入过的点(已经分配了序号)
我的代码:一开始建图是1~n(所有点),后面重新建图是按照加入到vector gast里面的顺序0~n
调试了挺久。。。各种错误T T 好弱好弱啊
#include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <queue> #include <map> #include <string> #include <cstring> #include <algorithm> using namespace std; const int maxn = 6000; const int maxm = 6090; const int inf = ~0u >> 2; struct Edge{ int v, w; Edge() {} Edge(int v, int w) { this->v = v; this->w = w; } }; int n, m, gas, ncnt; vector<int> gast; vector<Edge> g1[maxn], g2[maxm]; map<string, int> mp; void addNode(string s) { if(!mp[s]) mp[s] = ++ncnt; } void addEdge(int u, int v, int w) { g1[u].push_back(Edge(v, w)); g1[v].push_back(Edge(u, w)); } void spfa(int x, int dis[], vector<Edge> g[]) { queue<int> q; bool inqueue[maxn]; memset(inqueue, 0, sizeof(inqueue)); inqueue[x] = 1; q.push(x); dis[x] = 0; while(!q.empty()) { int tmp = q.front(); q.pop(); inqueue[tmp] = false; for(int i = 0; i < g[tmp].size(); i++) { int v = g[tmp][i].v, w = g[tmp][i].w; if(dis[tmp]+w < dis[v]) { dis[v] = dis[tmp]+w; if(!inqueue[v]) { q.push(v); inqueue[v] = true;; } } } } } int main() { #ifdef LOCAL freopen("D.in", "r", stdin); #endif while(scanf("%d%d%d", &m, &n, &gas) != EOF) { if(m == 0 && n == 0) break; ncnt = 0; char stmp[maxm], estmp[maxm]; gast.clear(); mp.clear(); for(int i = 0; i < maxn; i++) g1[i].clear(); for(int i = 0; i < maxm; i++) g2[i].clear(); scanf("%s%s", stmp, estmp); addNode(stmp); addNode(estmp); for(int i = 0; i < m; i++) { int w; scanf("%s%s%d", stmp, estmp, &w); addNode(stmp); addNode(estmp); addEdge(mp[stmp], mp[estmp], w); } gast.push_back(1); gast.push_back(2); for(int i = 1; i <= n; i++) { //if one vertex is unique, ignore it scanf("%s", stmp); if(mp[stmp]) gast.push_back(mp[stmp]); } //calc single-point shortest path for every gas station and set-up point //rebuild a graph with vertices including stations and beginning and end point for(int i = 0; i < gast.size(); i++) { int x = gast[i]; int dis[maxn]; fill(dis, dis+ncnt+1, inf); spfa(x, dis, g1); for(int j = 0; j < gast.size(); j++) if(dis[gast[j]] <= gas*10) g2[i].push_back(Edge(j, dis[gast[j]])); } int dis[maxm]; fill(dis, dis+gast.size()+1, inf); spfa(0, dis, g2); printf("%d ", dis[1] != inf ? dis[1] : -1); } return 0; }
N = 14 真该往状压dp去想= =
先预处理出每个串放其他串后面会增加的长度(奥 先剔除子串 可以保证一个串不会覆盖到第三个串去)
然后我们可以想到f[i]表示已经选了state=i这些串的最短长度,然后再放一个串到后面去
只需要再添加一维f[i][j]表示以j串结尾,就能update (以上只是模拟可能想到此题思路的一种思维过程。。。)
奥 需要注意的是更新的时候 如果f[i][j]没有计算 就直接赋值 如果已经算出来了就 取最小值(因为可以由多种状态去update这个状态)
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> using namespace std; const int maxn = 30; int n; int extra[maxn][maxn], f[1<<15][maxn]; char word[maxn][maxn]; bool substr[maxn]; vector<char*> wd; int main() { #ifdef LOCAL freopen("F.in", "r", stdin); #endif while(scanf("%d", &n) != EOF) { if(n == 0) break; memset(substr, 0, n*sizeof(char)); wd.clear(); for(int i = 0; i < n; i++) { scanf("%s", word+i); for(int j = 0; j < i; j++) { if(strstr(word[i], word[j]) != NULL) substr[j] = true; else if(strstr(word[j], word[i]) != NULL) substr[i] = true; } } for(int i = 0; i < n; i++) if(!substr[i]) wd.push_back(word[i]); for(int i = 0; i < wd.size(); i++) for(int j = 0; j < wd.size(); j++) { int plen = strlen(wd[i]), nlen = strlen(wd[j]), match = 0; for(int k = min(nlen, plen); k > 0; k--) if(strncmp(wd[j], wd[i]+plen-k, k) == 0) { match = k; break; } extra[i][j] = nlen-match; } int cnt = wd.size(); memset(f, 0, sizeof(f)); for(int i = 0; i < cnt; i++) f[1<<i][i] = strlen(wd[i]); for(int i = 1; i < (1 << cnt); i++) for(int j = 0; j < cnt; j++) { if(((1<<j)&i) == 0) continue; for(int k = 0; k < cnt; k++) { if((1<<k)&i) continue; int now = i|(1<<k); f[now][k] = f[now][k]? min(f[now][k], f[i][j]+extra[j][k]):f[i][j]+extra[j][k]; // if(i == 13) // cout << "Insert " << k << " after " << j << ' ' << f[now][k] << endl; } } int ans = cnt*maxn; for(int i = 0; i < cnt; i++) ans = min(ans, f[(1<<cnt)-1][i]); printf("%d ", ans); } return 0; }
卡了4天终于把坑补上了。。还不算J题压根没看
训练时A题写了一遍WA就没心情写了,其实呢...B题还是可以尝试一发的
就越来越弱哎~