被自己蠢哭了。。。。

250-point problem

國際象棋棋盤上給出兩個坐標，問象從一個走到還有一個最少要幾步。

黑格象僅僅能走黑格，白格象僅僅能走白格，僅僅要推斷兩個坐標的顏色是否同樣就能推斷是否可達，觀察棋盤能夠發現坐標的奇偶性決定了格子的顏色;可達的情況下最多兩步就能達到，所以僅僅要推斷格子是否在同一條斜線上即可了。

#include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<ctime> #include<cctype> #include<cmath> #include<string> #include<cstring> #include<stack> #include<queue> #include<list> #include<vector> #include<map> #include<set> #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #define maxm #define maxnusing namespace std;class BishopMove { public:int howManyMoves(int r1, int c1, int r2, int c2){if (r1==r2 && c1==c2) return 0;if (((r1+c1)&1) == ((r2+c2)&1)){if (abs(r1-r2)==abs(c1-c2)) return 1;return 2;}return -1;} };int main() {#ifndef ONLINE_JUDGEfreopen("/home/fcbruce/文檔/code/t","r",stdin);#endif // ONLINE_JUDGEreturn 0; }

500-point problem

給出一個括號序列，X可被括號替換，問這串序列是否可能合法。由于當時沒看見X的數量不超過5就用了區間DP，有一處下標竟然沒控制好結果RE。。。。事實上能夠用DFS求出全部可能的序列，然后用棧推斷;區間DP僅僅要求出對這段序列最少加多少括號使其合法即可，假設為0就是合法的，要注意對匹配括號的推斷。

#include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<ctime> #include<cctype> #include<cmath> #include<string> #include<cstring> #include<stack> #include<queue> #include<list> #include<vector> #include<map> #include<set> #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #define maxm #define maxnusing namespace std;class BracketExpressions { public:bool check(char x,char y){if (x=='(' && y==')' || x=='['&& y==']' ||x=='{' && y=='}')return true;if (x=='X' && (y==']' || y=='}' || y==')' || y=='X')) return true;if (y=='X' && (x=='(' || x=='[' || x=='{')) return true;return false;}string ifPossible(string str){int l=str.size();int dp[60][60];memset(dp,0,sizeof dp);for(int i = 0; i<l; i++){dp[i][i] = 1;}for (int m=1;m<l;m++){for (int i=0;i<l;i++){int j=i+m;if (j>=l) break;dp[i][j]=INF;if (check(str[i],str[j]))dp[i][j]=min(dp[i][j],dp[i+1][j-1]);for (int k=i;k<j;k++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);}}}if (dp[0][l-1]==0) return "possible";elsereturn "impossible";} };int main() {#ifndef ONLINE_JUDGEfreopen("/home/fcbruce/文檔/code/t","r",stdin);#endif // ONLINE_JUDGEreturn 0; }

1000-point problem

時間不夠，比賽的時候沒來得及敲完。。。。。

題意：

給出一個有n個元素的集合E={ x | 0<=x<n , x為整數 },和一段序列f={ xi | 0<=xi,i<n },對于集合E的子集S，有隨意i屬于S，f[i]=xi 也屬于S，問這種子集有多少個。

分析：

這事實上是個圖論。

對于每一個i，都相應一個f[i]=xi,假設我取i，那我必然也要取f[i]=xi，即i依賴于f[i]=xi。于是建立有向邊i---->f[i]=xi;對于圖中的每一個強聯通分量，這個分量中的全部點一定是同一時候取的。我們能夠進行強聯通縮點(tarjan)，剩下的DAG中每一個點都有取和不取兩種關系。應用乘法原理和加法原理，反向建圖后通過樹形DP求得最后的方案數：對于節點u，取這個節點的方案數是它全部子節點的方案數相乘，不取這個節點的方案數為1。

#include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<ctime> #include<cctype> #include<cmath> #include<string> #include<cstring> #include<stack> #include<queue> #include<list> #include<vector> #include<map> #include<set> #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #define maxm 555555 #define maxn 55using namespace std;int fir[maxn]; int u[maxm],v[maxm],nex[maxm]; long long w[maxn]; int n;int pre[maxn],low[maxn],sccno[maxn]; int st[maxn],top; int dfs_clock,scc_cnt;int deg[maxn];void tarjan_dfs(int _u) {pre[_u]=low[_u]=++dfs_clock;st[++top]=_u;for (int e=fir[_u];e!=-1;e=nex[e]){int _v=v[e];if (pre[_v]==0){tarjan_dfs(_v);low[_u]=min(low[_u],low[_v]);}else{if (sccno[_v]==0)low[_u]=min(low[_u],pre[_v]);}}if (low[_u]==pre[_u]){scc_cnt++;while (true){int x=st[top--];sccno[x]=scc_cnt;if (x==_u) break;}} }void find_scc() {dfs_clock=scc_cnt=0;top=-1;memset(sccno,0,sizeof sccno);memset(pre,0,sizeof pre);for (int i=0;i<n;i++){if (pre[i]==0) tarjan_dfs(i);} }long long dfs(int _u) {long long temp=1;for (int e=fir[_u];~e;e=nex[e]){temp*=dfs(v[e]);}return temp+1; }class InvariantSets { public:long long countSets(vector <int> f){n=f.size();memset(fir,-1,sizeof fir);for (int i=0;i<n;i++){u[i]=i;v[i]=f[i];nex[i]=fir[i];fir[i]=i;}find_scc();memset(fir,-1,sizeof fir);memset(deg,0,sizeof deg);int e=0;for (int i=0;i<n;i++){if (sccno[u[i]]==sccno[v[i]]) continue;u[e]=sccno[u[i]];v[e]=sccno[v[i]];swap(u[e],v[e]);nex[e]=fir[u[e]];deg[v[e]]++;fir[u[e]]=e++;}for (int i=1;i<=scc_cnt;i++){if (deg[i]==0){u[e]=i;v[e]=0;swap(u[e],v[e]);nex[e]=fir[u[e]];fir[u[e]]=e++;}}return dfs(0)-1;} };int main() {#ifndef ONLINE_JUDGEfreopen("/home/fcbruce/文檔/code/t","r",stdin);#endif // ONLINE_JUDGEInvariantSets a;itn x,y;while (~scanf("%d",&x)){vector <int> v;for (int i=0;i<x;i++){scanf("%d",&y);v.push_back(y);}printf("%lld\n",a.countSets(v));}return 0; }

轉載于:https://www.cnblogs.com/mfrbuaa/p/4265632.html

總結

以上是生活随笔為你收集整理的Topcoder SRM 628 DIV 2的全部內容，希望文章能夠幫你解決所遇到的問題。

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