首页 > 代码库 > Topcoder SRM 648 (div.2)
Topcoder SRM 648 (div.2)
第一次做TC全部通过，截图纪念一下。
终于蓝了一次，也是TC上第一次变成蓝名，下次就要做Div.1了，希望div1不要挂零。。。_(:зゝ∠)_
A. KitayutaMart2
万年不变的水题。
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,num;bool flag;class KitayutaMart2{ public: int numBought(int K, int T) { m=T/K; m++; ans=0; while (m!=0) { m>>=1; ans++; } return ans-1; }};
B. Fragile2
给一个N个点（3<=N<=20）的无向图，现在不分先后取出其中两个点，使得强连通分量变多，问最多有多少种取法。
因为图实在太小了，所以枚举这两个点即可。用DFS计算连通分支数。
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,num,G[55][55],G2[55][55];bool flag;int vis[55];class Fragile2{ public: void check(int u) { int i,j,k; for (i=0;i<n;i++) { if (!vis[i] && G2[u][i]) { vis[i]=1; check(i); } } } int cc(int a,int b)//计算删去结点a,b后的连通度 { int i,j,k,blk; memset(vis,0,sizeof(vis)); for (i=0;i<n;i++)//复制一下地图 { for (j=0;j<n;j++) { G2[i][j]=G[i][j]; } } vis[a]=1;vis[b]=1;//删去结点a,b for (i=0;i<n;i++) { G2[i][a]=0; G2[a][i]=0; G2[b][i]=0; G2[i][b]=0; } blk=0; for (i=0;i<n;i++)//计算强连通分量 { if (!vis[i]) { blk++; vis[i]=1; check(i); } } return blk; } int countPairs(vector <string> mp) { int i,j,k; n=mp.size(); for (i=0;i<n;i++)//复制一下地图到G { for (j=0;j<n;j++) { if (mp[i][j]==‘N‘) G[i][j]=0; else G[i][j]=1; } } num=cc(n,n);//计算一下不修改地图时的强连通分量数 ans=0; for (i=0;i<n;i++)//枚举要删除的两个点。 { for (j=i+1;j<n;j++) { if (num<cc(i,j)) ans++; } } return ans; }};
C.ABC
字符串长为N（3<=N<=30），并且由大写字母A,B,C组成，其中存在K（k<=N*(N-1)/2）对数i和j，满足i<j，s[i]<s[j]。现在给出N,K，试着构造任意一个满足条件的字符串
动态规划，设dp[a][b][c][s]!=0时为当前字符串由a个字母A，b个字母b，c个字母C组成，并且得分为s成立。而dp[a][b][c][s]=0表示由a个字母A，b个字母b，c个字母C组成的字符串不可能得分为s。
转移方程
(1) dp[a+1][b][c][s]=dp[a][b][c][s];
(2) dp[a][b+1][c][s+a]=dp[a][b][c][s]
(3) dp[a][b][c+1][s+a+b]=dp[a][b][c][s]
初始状态为dp[0][0][0][0]=1
因为我们要递归输出，所以设dp[a][b][c][s]=1为由状态1转移过来的，dp[a][b][c][s]=2为由状态2转移过来的，dp[a][b][c][s]=3为由状态3转移过来的
最后递归输出答案即可。
#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 1005#define MAXM 40005#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,big,cas,num;bool flag;int dp[35][35][35][440];string ans;class ABC{ public: void out(int x,int y,int z,int s) { if (x<=0&&y<=0&&z<=0&&s<=0) return; if (dp[x][y][z][s]==1) { out(x-1,y,z,s); ans+="A"; }else if (dp[x][y][z][s]==2) { out(x,y-1,z,s-x); ans+="B"; }else { out(x,y,z-1,s-x-y); ans+="C"; } } string createString(int n, int c) { int i,j,k,l; dp[0][0][0][0]=1; for (i=0;i<=n;i++) { for (j=0;i+j<=n;j++) { for (k=0;i+j+k<=n;k++) { for (l=0;l<=c;l++) { if (dp[i][j][k][l]) { if (i+j+k==n && l==c)//找到答案，输出 { out(i,j,k,l);//递归输出 return ans; } dp[i+1][j][k][l]=1; if (l+i<=c) dp[i][j+1][k][l+i]=2; if (l+i+j<=c) dp[i][j][k+1][l+i+j]=3; } } } } } return ""; }
Topcoder SRM 648 (div.2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。