A:小Y做家教

簡單的想法題。使用hash表或者是map存儲所有數，然后從最小的數開始找從這個數開始的連續P倍數的個數X，那么需要刪除的數的個數為X/2。

代碼如下：

Problem A

?

B:小Y的難題Ⅰ

組合數學題，通過經典的一一對應原則推導出答案為N^(N-2)。http://wenku.baidu.com/view/2e1ab2757fd5360cba1adbba.html
Cayley定理在組合數學中的應用。

代碼如下：

Problem B #include <iostream> #include <cmath> #include <cstring> #include <cstdio> #include <string> #include <stdlib.h> using namespace std; typedef long long LL; const LL M=1e9+7; LL Pow( LL a, LL b) {LL ans=1;while( b ){if( b&1 ){ans*=a;ans%=M;}a*=a;a%=M;b>>=1; }return ans; } int main( ) {LL N;while( scanf( "%lld", &N )!=EOF ){printf( "%lld\n", Pow( N, N-2 ) );}return 0; }

?

C:小Y的逆襲

計算幾何。該題一個簡單的做法是先找出三個點的外心，然后用極坐標每次旋轉72°生成剩下的點。

代碼如下：

Problem C #include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> #include <iostream> #include <cmath> #include <vector> using namespace std;const double PI = acos(-1);struct point{double x,y;}; struct line{point a,b;}; vector<point>v;point p[3], cc;point intersection(line u,line v){point ret=u.a;double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));ret.x+=(u.b.x-u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;return ret; }point circumcenter(point a,point b,point c){line u,v;u.a.x=(a.x+b.x)/2;u.a.y=(a.y+b.y)/2;u.b.x=u.a.x-a.y+b.y;u.b.y=u.a.y+a.x-b.x;v.a.x=(a.x+c.x)/2;v.a.y=(a.y+c.y)/2;v.b.x=v.a.x-a.y+c.y;v.b.y=v.a.y+a.x-c.x;return intersection(u,v); }double dist(point a, point b) {return sqrt(double( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) )); }bool cmp(point a, point b) {if (fabs(a.x - b.x) > 1e-6) {return a.x < b.x;} else {return a.y < b.y;} }int main() {double R;point info;while (scanf("%lf %lf", &p[0].x, &p[0].y) != EOF) {v.clear();for (int i = 1; i < 3; ++i) {scanf("%lf %lf", &p[i].x, &p[i].y);}cc = circumcenter(p[0], p[1], p[2]);R = dist(p[0], cc);double phi = atan2(p[0].y-cc.y, p[0].x-cc.x); // 求出第一個點的角度for (int i = 0; i < 5; ++i) {info.x = R * cos(phi) + cc.x, info.y = R * sin(phi) + cc.y;v.push_back(info);phi += 72.0*PI/180.0;}sort(v.begin(), v.end(), cmp);for (int i = 0; i < 5; ++i) {int flag = 0;for (int j = 0; j < 3; ++j) {if (fabs(v[i].x - p[j].x) < 1e-6 && fabs(v[i].y - p[j].y) < 1e-6) {flag = 1;break;}}if (!flag) {printf("%.2f %.2f\n", v[i].x, v[i].y);}}}return 0; }

?

D:Palindrome

動態規劃。題意是求將一個串改造成回文串的最少花費。給出所有組成串的字母添加和刪除的花費。設dp[i][j]表示[i,j]子串被改造成回文串的最少開銷是多少。那么有動態規劃方程：
dp[i][j]?=?min(dp[i+1][j]?+?cost[i],?dp[i][j-1]?+?cost[j]);?其中cost[i]?=?min(add[i],?del[i])存儲刪除和添加節點的較小的花費。如果str[i]?==?str[j]的話就多出一種選擇dp[i-1][j-1]。

代碼如下：

Problem D #include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std; int N, M, dp[2005][2005]; int cost[30]; char str[2005];int DP() {for (int i = 1; i < M; ++i) {for (int j = 1; j+i <= M; ++j) {int a = j, b = j + i, ll = str[a]-'a', rr = str[b]-'a';dp[a][b] = min(dp[a+1][b] + cost[ll], dp[a][b-1] + cost[rr]);if (ll == rr)dp[a][b] = min(dp[a][b], dp[a+1][b-1]);}}return dp[1][M]; }int main() {char s[5];int a, b;while (scanf("%d %d", &N, &M) == 2) {scanf("%s", str+1);for (int i = 1; i <= N; ++i) {scanf("%s %d %d", s, &a, &b);cost[s[0]-'a'] = min(a, b);}printf("%d\n", DP());}return 0; }

?

E:小Y的難題Ⅱ

分解素因子，轉換成M個球放到N個盒子模型，得出組合公式C(N+M-1,?N-1),因為ai>1,既盒子不允許為空，所以求出總方案數后，減去盒子為空的情形。對于盒子為空的求解，通過假設至少一個盒子（C(N+M-1-1,M-1-1)），兩個，直到N-1個，由容斥來解決重復問題。注意單個素因子，其次數可能會很大，所以C預處理要比較大，不然會RE。

代碼如下：

Problem E #include<cstdio> #include<cstring> #include<cstdlib> #include<assert.h> #include<algorithm> #include<map> #include<cmath> using namespace std; typedef long long LL;const int mod = 1e9+7;int b[21], a[1010], n, tot; LL C[1100][1100];map<int,int>mp;void init(){for(int i = 0; i <= 1000; i++)C[i][0] = 1, C[i][i] = 1;for(int i = 2; i <= 1000; i++)for(int j = 1; j < i; j++)C[i][j] = (C[i-1][j-1]+C[i-1][j])%mod; }void deal(){mp.clear();for(int i = 0; i < n; i++){int tmp_max = (int)sqrt(1.*b[i]);int t = b[i];for(int j = 2; j <= tmp_max; j++){if( t%j == 0 ){if( mp.count(j) == 0 ) mp[j] = 0;int cnt = 0; while( t%j == 0 ) (t/=j), cnt++;mp[j] += cnt;} }if( t > 1 ){if( mp.count(t) == 0 ) mp[t] = 1;else mp[t]++;} }int idx = 0;memset( a, 0, sizeof(a));for( map<int,int>::iterator it = mp.begin(); it != mp.end(); it++ )a[idx++] = it->second;tot = mp.size(); } void solve(){LL ans = 0;for(int i = 0; i < n; i++){LL tmp = 1;for(int j = 0; j < tot; j++){ assert( (((n-1-i+a[j])>=0)&&(n-1-i+a[j])<=1000) ); tmp = tmp*C[ n-1-i+a[j] ][ n-1-i ]%mod; }tmp = tmp*C[n][i]%mod;if( i&1 ) tmp = -tmp;ans = (ans+tmp+mod)%mod;}printf("%lld\n", ans); } int main(){init();int T;scanf("%d", &T);while( T-- ){scanf("%d", &n);for(int i = 0; i < n; i++)scanf("%d", &b[i] );deal();solve();}return 0; }

?

F:War Ⅰ

并查集+最短路。通過并查集處理結盟的點，然后從集合中選擇一個到目標點最短的距離輸出。

代碼如下：

Problem F #include<iostream> #include<stdio.h> #include<string.h>using namespace std;const int inf = 0x7f7f7f7f; const int MAXV = 1002;int UFS[MAXV];int Find(int x) {return UFS[x]=(UFS[x]!=x?Find(UFS[x]):x); } void Union(int x,int y) {UFS[Find(x)]=Find(y); }char o; int n,m,k,u,v,w,x,y,a[MAXV][MAXV];int main() {while(scanf("%d %d %d",&n,&m,&k)!=EOF){memset(a,inf,sizeof(a));for(int i=0;n>i;i++){UFS[i]=i;}for(int i=0;m>i;i++){scanf("%d %d %d",&u,&v,&w);a[u][v]=min(a[u][v],w);}for(int z=0;n>z;z++){for(int i=0;n>i;i++){if(a[i][z]!=inf){for(int j=0;n>j;j++){if(a[z][j]!=inf){a[i][j]=min(a[i][j],a[i][z]+a[z][j]);}}}}}for(int i=0;k>i;i++){getchar();scanf("%c %d %d",&o,&x,&y);if(o=='I') Union(x,y);else{int ans=inf;for(int i=0;n>i;i++){if(Find(x)==Find(i)){ans=min(ans,a[i][y]);}}printf("%d\n",ans!=inf?ans:-1);}}}return 0; }

?

G:War Ⅱ

二分枚舉構圖+二分匹配。該題想說明的就是A中的一個城市只能夠對應B中的一個城市。先通過floyd求出任意城市之間的最短路，然后二分枚舉構好A->B城市的二分圖，然后使用匈牙利算法計算是否能夠達到完全匹配。

代碼如下：

Problem G #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <ctime> #include <cassert> using namespace std;const int MAX = 105; const int INF = 0x3f3f3f3f; int n, N, M, reca[MAX], recb[MAX]; int mp[MAX][MAX]; int marry[MAX]; char G[MAX][MAX]; char vis[MAX];void floyd() {for (int k = 0; k < n; ++k) {for (int i = 0; i < n; ++i) {if (mp[i][k] == INF || i == k) continue;for (int j = 0; j < n; ++j) {if (mp[k][j] == INF || j == k) continue;if (mp[i][j] > mp[i][k] + mp[k][j]) {mp[i][j] = mp[i][k] + mp[k][j];}}} } }bool path(int u) {for (int i = 0; i < M; ++i) {if (!G[u][i] || vis[i])continue;vis[i] = 1;if (marry[i] == -1 || path(marry[i])) {marry[i] = u;return true;}}return false; }void build(int lim) {memset(G, 0, sizeof (G));for (int i = 0; i < N; ++i) {for (int j = 0; j < M; ++j) {if (mp[reca[i]][recb[j]] <= lim) {G[i][j] = 1;}}} }bool Ac() {int cnt = 0;memset(marry, 0xff, sizeof (marry));for (int i = 0; i < N; ++i) {memset(vis, 0, sizeof (vis));if (path(i)) {++cnt;}}return cnt == M; }int bsearch(int l, int r) {int mid, ret;while (l <= r) {mid = (l + r) >> 1;build(mid);if (Ac()) {ret = mid;r = mid - 1; } else {l = mid + 1;}}return ret; }int main() {while (scanf("%d", &n) == 1) {for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {scanf("%d", &mp[i][j]);}}scanf("%d", &N);for (int i = 0; i < N; ++i) {scanf("%d", &reca[i]);--reca[i];}scanf("%d", &M);for (int i = 0; i < M; ++i) {scanf("%d", &recb[i]);--recb[i];}floyd();printf("%d\n", bsearch(0, 10000));}return 0; }

?

H:War Ⅲ

法一：通過題目給定的關系不難知道a[i]?=?3*a[i-1]?+?a[i-2]?-?3*a[i-3]。假設要求第D天的口令，那么計算出a[D-1],?a[D-2],?a[D-3]就能夠計算出a[D]，求出四個系數后，代入X便可求解答案了。這題D給的數據比較大，直接計算肯定會TLE，那么使用矩陣并加上快速降冪來計算就簡單多了，將給定的b,c,d作為3*1的矩陣B{a[0],?a[-1],?a[-2]}^-1，矩陣A=
3?1?-3
1?0?0
0?1?0
作為遞推矩陣，那么在B矩陣左邊乘上D-1個A最后的結果就是{a[D-1],?a[D-2],?a[D-3]}^-1，D-1個A相乘就可以使用矩陣快速冪了。

代碼如下：

Problem H #include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> #include <cassert> using namespace std;typedef long long int64; const int MOD = int(1e9)+7; int a, b, c, d, D, X;int64 R[3][3] = {{3, 1, -3},{1, 0, 0},{0, 1, 0} };struct Matrix {int64 mat[3][3];Matrix() {memset(mat, 0, sizeof (mat));}void unit() {memset(mat, 0, sizeof (mat));for (int i = 0; i < 3; ++i) {mat[i][i] = 1;}}void init() {memcpy(mat, R, sizeof (mat));}void show() const;friend Matrix operator * (const Matrix & a, const Matrix & b);friend Matrix pow(Matrix a, int b); };void Matrix::show() const {for (int i = 0; i < 3; ++i) {for (int j = 0; j < 3; ++j) {printf("%d ", mat[i][j]); }puts("");} }Matrix operator * (const Matrix & a, const Matrix & b) {Matrix ret;for (int i = 0; i < 3; ++i) {for (int j = 0; j < 3; ++j) {for (int k = 0; k < 3; ++k) {ret.mat[i][j] += (a.mat[i][k] * b.mat[k][j]) % MOD;ret.mat[i][j] %= MOD;}}}return ret; }Matrix pow(Matrix a, int b) {Matrix ret;ret.unit();while (b) {if (b & 1) {ret = ret * a;}a = a * a;b >>= 1;}return ret; }int64 cal(int64 na, int64 nb, int64 nc, int64 nd) {int64 ini[4] = {1};for (int i = 1; i < 4; ++i) {ini[i] = (ini[i-1] * X) % MOD;}return ((na*ini[3])%MOD+(nb*ini[2])%MOD+(nc*ini[1])%MOD+(nd*ini[0])%MOD)%MOD; }void solve() {Matrix mm; mm.init();mm = pow(mm, D-1);int64 na, nb, nc, nd;nb = ((mm.mat[0][0]*b)%MOD + (mm.mat[0][1]*c)%MOD + (mm.mat[0][2]*d)%MOD)%MOD;nc = ((mm.mat[1][0]*b)%MOD + (mm.mat[1][1]*c)%MOD + (mm.mat[1][2]*d)%MOD)%MOD;nd = ((mm.mat[2][0]*b)%MOD + (mm.mat[2][1]*c)%MOD + (mm.mat[2][2]*d)%MOD)%MOD;na = (3*nb)%MOD+nc-(3*nd)%MOD;printf("%d\n", int((cal(na, nb, nc, nd)+MOD)%MOD)); }int main() {while (scanf("%d %d %d %d", &a, &b, &c, &d) != EOF) {assert(a >= 0 && a <= 100);scanf("%d %d", &D, &X);solve();}return 0; }

?

法二：根據表達式a[i]?=?3*a[i-1]?+?a[i-2]?-?3*a[i-3]，由于該表達式為常系數3階齊次遞推關系，因此設a[n]?=?r^n，代入方程求出特征根為-1,1,3，因此a[n]=A*(-1)^n+B*(1)^n+C*(3)^n，令a[0]=d,a[1]=c,a[2]=b求出A,B,C之后再根據通項公式求出D天后的系數。b,c,d是8的倍數保證了解三元一次方程組時不會出現分數。

代碼如下：

Problem H #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std;typedef long long int64; const int64 MOD = (int64)1e9 + 7; int64 a, b, c, d, D, X;int64 _pow(int64 a, int64 b) {int64 ret = 1;while (b) {if (b & 1) {ret *= a;ret %= MOD;}b >>= 1;a *= a;a %= MOD;}return ret; }int64 cal(int64 na, int64 nb, int64 nc, int64 nd) {int64 ini[4] = {1};for (int i = 1; i < 4; ++i) {ini[i] = (ini[i-1] * X) % MOD;}return ((na*ini[3])%MOD+(nb*ini[2])%MOD+(nc*ini[1])%MOD+(nd*ini[0])%MOD)%MOD; }int main() {while (scanf("%lld %lld %lld %lld", &a, &b, &c, &d) != EOF) {scanf("%lld %lld", &D, &X);int64 A = (3*d-4*c+b)/8;int64 B = (3*d+2*c-b)/4;int64 C = (b-d)/8;a = (A * ((D+2) & 1 ? -1 : 1) + B + C * _pow(3, D+2)) % MOD;b = (A * ((D+1) & 1 ? -1 : 1) + B + C * _pow(3, D+1)) % MOD;c = (A * ((D) & 1 ? -1 : 1) + B + C * _pow(3, D)) % MOD;d = (A * ((D-1) & 1 ? -1 : 1) + B + C * _pow(3, D-1)) % MOD;printf("%lld\n", (cal(a, b, c, d)+MOD)%MOD);}return 0; }

?

轉載于:https://www.cnblogs.com/Lyush/archive/2013/03/30/2990715.html

總結

以上是生活随笔為你收集整理的2013ACM多校联合（2）的全部內容，希望文章能夠幫你解決所遇到的問題。

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