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 0x3fffffff
using 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 0x3fffffff
using 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 0x3fffffff
using 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";}elseif (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 "";}

?