1002 Warm up
这题不难,关键是怎么去缩点和扩栈。
#include <cstdio> #include <cstring> #include <vector> #include<queue> #include<cmath> #include <algorithm> using namespace std; #define MAXN 200006 #define MAXM 2000006 #pragma comment(linker, "/STACK:1024000000,1024000000") struct node { int v, w, pre; } edge[MAXM]; int pos[MAXN], nEdge; //图的存储:链式前向星(池子法) struct Bridge { int u, v; } bridge[MAXM]; //用来记录桥 int tot; //桥的个数 int fa[MAXN], cc; //fa:各个点所属的缩点(连通块),cc连通块的个数 int dfn[MAXN], low[MAXN], Time; //时间戳 int stack[MAXN], top; //用于维护连通块的 int n, m; //点的个数和边的条数 void connect(int u, int v, int w) { nEdge++; edge[nEdge].pre = pos[u]; edge[nEdge].v = v; edge[nEdge].w = w; pos[u] = nEdge; } vector<int> graph[MAXN]; void tarjan(int cur, int from, int from_edge) { low[cur] = dfn[cur] = Time++; stack[++top] = cur; for (int p=pos[cur]; p; p=edge[p].pre) { int v = edge[p].v; if (v == from&&abs(p-from_edge)<=1) continue; //注意一下这里 if (!dfn[v]) { tarjan(v, cur, p); if (low[v] < low[cur]) low[cur] = low[v]; if (low[v] > dfn[cur]) { bridge[tot].u = cur; bridge[tot++].v = v; cc++; graph[cc].clear(); do { fa[stack[top]] = cc; } while (stack[top--] != v); } } else if (low[cur] > dfn[v]) low[cur] = dfn[v]; } } int bfs(int x,int flag) { queue<int> q; int y; q.push(x); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); low[x]=0; dfn[x]=1; while(q.size()>0) { y=q.front(); // printf("%d\n",y); q.pop(); for(int i=0;i<graph[y].size();i++) { int z=graph[y][i]; if(!dfn[z]) { dfn[z]=1; low[z]=low[y]+1; q.push(z); } } } if(flag) return y; return low[y]; } int main() { while(scanf("%d%d", &n, &m),n+m) { memset(pos, 0, sizeof(pos)); nEdge = 0; int u, v, w; for (int i=0; i<m; i++) { scanf("%d%d", &u, &v); connect(u, v, 1); connect(v, u, 1); } memset(dfn, 0, sizeof(dfn)); memset(fa, -1, sizeof(fa)); cc = tot = 0; for (int i=1; i<=n; i++) if (!dfn[i]) { top = Time = 1; tarjan(i, -1, -3); ++cc; graph[cc].clear(); for (int j=1; j<=n; j++) if (dfn[j] && fa[j]==-1) fa[j] = cc; } for(int i=0;i<tot;i++) { graph[fa[bridge[i].u]].push_back(fa[bridge[i].v]); graph[fa[bridge[i].v]].push_back(fa[bridge[i].u]); } int y=bfs(1,1); int ans2=bfs(y,0); // printf("%d %d\n",cc,ans2); printf("%d\n",cc-1-(ans2)); } return 0; }
1008 Palindrome Sub-Array
求n*m的矩阵中的回文方阵,由于写了四个for,所以很担心会超时,所以加了l判断长度来压缩时间,最后竟然压到了100ms,一种很开心的感觉。
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <string> #include <algorithm> #include <vector> #include <queue> #include <map> using namespace std; int s[305][305]; int n,m; int l; int ans; int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { scanf("%d",&s[i][j]); } } ans = 1; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { if(min(n-i,m-j) <= ans) { break; } l = min(n-i,m-j); while(l > ans)//判断是否是回文方阵 { if(s[i][j]==s[i+l-1][j]&&s[i+l-1][j]==s[i][j+l-1]&&s[i][j+l-1]==s[i+l-1][j+l-1]) { int q = 0; for(int k = 1; k * 2 < l; k++) { if(s[i+k][j]==s[i+l-1-k][j]&&s[i+l-1-k][j]==s[i+k][j+l-1]&&s[i+k][j+l-1]==s[i+l-1-k][j+l-1]) { if(s[i][j+k]==s[i+l-1][j+k]&&s[i+l-1][j+k]==s[i][j+l-1-k]&&s[i][j+l-1-k]==s[i+l-1][j+l-1-k]) { if(s[i+k][j+k]==s[i+l-1-k][j+k]&&s[i+l-1-k][j+k]==s[i+k][j+l-1-k]&&s[i+k][j+l-1-k]==s[i+l-1-k][j+l-1-k]) { continue; } else { q = 1; break; } } else { q = 1; break; } } else { q = 1; break; } for(int c = k - 1; c > 0; c--) { if(s[i+k][j+c]==s[i+l-1-k][j+c]&&s[i+l-1-k][j+c]==s[i+k][j+l-1-c]&&s[i+k][j+l-1-c]==s[i+l-1-k][j+l-1-c]) { if(s[i+c][j+k]==s[i+l-1-c][j+k]&&s[i+l-1-c][j+k]==s[i+c][j+l-1-k]&&s[i+c][j+l-1-k]==s[i+l-1-c][j+l-1-k]) { continue; } else { q = 1; break; } } else { q = 1; break; } } if(q == 1) { break; } } if(q == 0) { ans = l; //cout<<i<<' '<<j<<' '<<l<<'c'<<endl; } } l--; } } } printf("%d\n",ans); } return 0; }
1009 Warm up 2
本场最水的一道题,不多说了。
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 2505 #define inf 1<<28 #define LL(x) ( x << 1 ) #define RR(x) ( x << 1 | 1 ) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) #define mp(a,b) make_pair(a,b) #define PII pair<int,int> using namespace std; inline void RD(int &ret) { char c; do { c = getchar(); } while(c < '0' || c > '9') ; ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); } int Map[1111][1111] ; int link[1111] ; bool vis[1111] ; int n , m ,s, v; int dfs(int now) { for (int i = 1 ;i <= m ;i ++) { if(Map[now][i]) if(!vis[i]) { vis[i] = 1 ; if(link[i] == -1 || dfs(link[i])) { link[i] = now ; return 1 ; } } } return 0 ; } int x1[1111], y1[1111] ; int x2[11111],y2[1111] ; bool check(int i , int j){ if(x1[i] <= x2[j] && x2[j] <= x1[i] + 1){ if(y2[j] <= y1[i] && y2[j] + 1 >= y1[i]){ return 1 ; } } return 0 ; } int main() { while(scanf("%d%d",&n,&m) , (n + m)){ mem(Map,0) ; mem(link , -1) ; for (int i = 1 ; i <= n ;i ++ ){ scanf("%d%d",&x1[i] ,&y1[i]) ; } for (int i = 1 ; i <= m ;i ++ ){ scanf("%d%d",&x2[i] , &y2[i]) ; } for (int i = 1 ; i <= n ; i ++ ){ for (int j = 1 ; j <= m ;j ++ ){ Map[i][j] = check(i , j ) ; } } int ans = 0 ; for (int i = 1 ; i <= n ;i ++){ mem(vis, 0 ) ; ans += dfs(i) ; } cout << n + m - ans << endl; } return 0 ; }