本文主要是介绍Topcode SRM 556，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Topcode SRM 556
没做这次tc，本来计划好要做的，记过被早上七点就起来帮老师排号的事儿忙昏了，把这事儿忘了，上qq的时候才看到群里人谈tc才恍然大悟，立马注册发现已经来不及了……哎，没做就没做，也没有什么遗憾的，至少不会掉ranking
div2 A 水题，顺着题目的思路暴力模拟，然后暴力统计即可
public:int find(vector <string> A){bool vis[55][55]={0};int n=sz(A),m=sz(A[0]);for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(A[i][j]=='N') vis[i][j+1]=1;else if(A[i][j]=='S') vis[i+2][j+1]=1;else if(A[i][j]=='W') vis[i+1][j]=1;else vis[i+1][j+2]=1;int ret=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!vis[i][j]) ret++;return ret;}div2 B 开始没有思路，想到到达每个点的XOR有很多，我们不能简单只取改点XOR最大的，这样结果很有可能不是最优的，因为改点XOR小的也可能经过一段路径之后XOR变大了；突破点就在于每个点的val 都在[ 0 ,1023]之间，那么这些数的XOR肯定在[0 ,1023] 范围内，然后每个节点的状态就有[ 0 ,1023]共1024个，然后开个数组记录是否可达就行了，用bfs（）实现
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
#define PB push_back
#define MP make_pair
#define ff first
#define ss second
#define two(w) (1<<w)
#define sz(v) (int)v.size()
#define all(c) c.begin(),c.end()
#define clr(buf,val) memset(buf,val,sizeof(buf))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define repv(i,v) for(int i=0;i<(int)v.size();i++)bool dp[50][1024],vis[50][1024],g[50][50];class XorTravelingSalesman
{public:int maxProfit(vector <int> val, vector <string> roads){int n=sz(val);for(int i=0;i<n;i++)for(int j=0;j<n;j++) g[i][j]=(roads[i][j]=='Y');memset(vis,0,sizeof(vis));clr(dp,0);queue<pair<int,int> > q;dp[0][val[0]]=1;for(q.push(MP(0,val[0]));!q.empty();q.pop()){int u=q.front().first;int v=q.front().second;vis[u][v]=0;for(int i=0;i<n;i++)if(g[u][i]&&!dp[i][v^val[i]]&&!vis[i][v^val[i]]) dp[i][v^val[i]]=1,vis[i][v^val[i]]=1,q.push(MP(i,v^val[i]));}int ret=0;for(int i=0;i<n;i++)for(int j=0;j<1024;j++)if(dp[i][j]&&ret<j) ret=j;return ret;}
div2 C 很容易想到用dp，每个数字明显只有两种选择，一个上放在最后面，一个是放在最前面，而且是限制的，要求最终的数不能包含前导0，比如答案可能是：100000012
0可以放在中间的，所以每个节点要记录该字符之前所有字符（包括该字符）所能组成的合法的数字的最小字符串，和非法的最小字符串，然后状态转移就很简单了
我用的$来标示该状态不存在
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
#define PB push_back
#define MP make_pair
#define ff first
#define ss second
#define two(w) (1<<w)
#define sz(v) (int)v.size()
#define all(c) c.begin(),c.end()
#define clr(buf,val) memset(buf,val,sizeof(buf))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define repv(i,v) for(int i=0;i<(int)v.size();i++)string dp[50][2];class LeftRightDigitsGame
{public:string ins_f(string a,char c){if(a=="$") return "$";string tmp="";tmp+=c;for(int i=0;i<a.length();i++) tmp+=a[i];return tmp;}string ins_b(string a,char c){if(a=="$") return "$";string tmp="";for(int i=0;i<a.length();i++) tmp+=a[i];tmp+=c;return tmp;}string Max(string a,string b){if(a=="$") return b;if(b=="$") return a;if(a<b) return a;return b;}string minNumber(string dig){int n=dig.length();if(dig[0]=='0'){dp[0][0]="$";dp[0][1]="0";}else {dp[0][0]=dig[0];dp[0][1]="$";}// cout<<dp[0][0]<<" "<<dp[0][1]<<endl;for(int i=1;i<n;i++){if(dig[i]!='0'){dp[i][0]=ins_f(dp[i-1][1],dig[i]);dp[i][0]=Max(dp[i][0],ins_f(dp[i-1][0],dig[i]));dp[i][0]=Max(dp[i][0],ins_b(dp[i-1][0],dig[i]));dp[i][1]=ins_b(dp[i-1][1],dig[i]);}else{dp[i][0]=ins_b(dp[i-1][0],dig[i]);dp[i][1]=ins_f(dp[i-1][0],dig[i]);dp[i][1]=Max(dp[i][1],ins_f(dp[i-1][1],dig[i]));dp[i][1]=Max(dp[i][1],ins_b(dp[i-1][1],dig[i]));}//cout<<dp[i][0]<<" "<<dp[i][1]<<endl;}return dp[n-1][0];}
这篇关于Topcode SRM 556的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
