Codeforces Round #261 (Div. 2)[ABCDE]
ACM
題目地址:Codeforces Round #261 (Div. 2)
A - Pashmak and Garden
題意：
一個(gè)正方形，它的邊平行于坐標(biāo)軸，給出這個(gè)正方形的兩個(gè)點(diǎn)，求出另外兩個(gè)點(diǎn)。
分析：
判斷下是否平行X軸或平行Y軸，各種if。
代碼：
/** Author: illuz * File: A.cpp* Create Date: 2014-08-15 23:35:17* Descripton: */#include #include #include #include using namespace std;const int N = 0;int main() { int x1, y1, x2, y2, x3, y3, x4, y4; int a; while (cin >> x1 >> y1 >> x2 >> y2) { if (x1 == x2) { a = y1 - y2; cout << x1 + a << ' ' << y1 << ' ' << x2 + a << ' ' << y2 << endl; } else if (y1 == y2) { a = x1 - x2; cout << x1 << ' ' << y1 + a << ' ' << x2 << ' ' << y2 + a << endl; } else { if (abs(x1 - x2) != abs(y1 - y2)) { cout << -1 << endl; continue; } cout << x1 << ' ' << y2 << ' ' << x2 << ' ' << y1 << endl; } } return 0;}
B - Pashmak and Flowers
題意：
在n個(gè)數(shù)中取出兩個(gè)數(shù)，使得差值最大，問(wèn)差值和有幾種取法。
兩種取法不同當(dāng)且僅當(dāng)：兩種方法至少有一個(gè)不同位置的數(shù)。
分析：
很明顯差值就是最大-最小。
如果兩個(gè)數(shù)不是相同的，那么取法就是max_cnt * min_cnt了。
如果相同就要注意了，因?yàn)閙ax_cnt * min_cnt里面有一些取法一樣的數(shù)。
比如：5 1 1 1 1 1。
- 那么我們可以這樣考慮，第一次可以取5種，第二次可以取(5-1)鐘，但是這里面(i,j)和(j,i)都取過(guò)，所以得減半，所以結(jié)果就是n*(n-1)/2。
- 或者可以這樣考慮，我們?yōu)榱瞬灰≈貜?fù)，規(guī)定第一次取的位置肯定在第二次前面，如果第一次取pos1，那么下次只能取(n-1)鐘；如果第一次取pos2，第二次就(n-2)....累計(jì)就是(n-1)*n/2了。
代碼：
/** Author: illuz * File: B.cpp* Create Date: 2014-08-15 23:51:15* Descripton: */#include #include #include #include using namespace std;#define repf(i,a,b) for(int i=(a);i<=(b);i++)typedef long long ll;const int N = 2e5 + 10;ll t, mmax, mmin;ll a[N];int main() { while (cin >> t) { repf (i, 0, t - 1) { cin >> a[i]; } sort (a, a + t); if (a[0] == a[t - 1]) { cout << 0 << ' ' << t * (t - 1) / 2 << endl; continue; } mmax = 0; mmin = 0; int i = 0; while (i < t && a[i] == a[0]) mmin++, i++; i = t - 1; while (i >= 0 && a[i] == a[t - 1]) mmax++, i--; cout << a[t - 1] - a[0] << ' ' << mmin * mmax << endl; } return 0;}
C - Pashmak and Buses
題意：
n個(gè)人坐車，有k輛車帶他們?nèi)個(gè)地方玩。問(wèn)怎么安排使得這d天他們沒(méi)有一對(duì)人一直在一起的（FFF團(tuán)的勝利）。
分析：
相當(dāng)于：d行n列，每個(gè)位置填一個(gè)1～k的整數(shù)，要求不能有兩列完全一樣。
爆搜過(guò)去即可，只要有解就行了。
代碼：
/** Author: illuz * File: C.cpp* Create Date: 2014-08-16 00:47:18* Descripton: */#include#include#include#include#include#includeusing namespace std;const int N = 1110;int a[N], sum;int n, d, k, m[N][N];void dfs(int x) { if(sum >= n) return; if(x >= d) { for (int i = 0; i < d; i++) m[i][sum] = a[i]; sum++; return; } for(int i = 1; i <= min(k, 1001); i++) { a[x] = i; dfs(x + 1); }}int main() { while (~scanf("%d%d%d", &n, &k, &d)) { memset(m, 0, sizeof(m)); sum = 0; dfs(0); if(sum < n) puts("-1"); else { for(int i = 0; i < d; i++) { for(int j = 0; j < n; j++) printf("%d ", m[i][j]); puts(""); } } } return 0;}
D - Pashmak and Parmida's problem
題意：
給出一些數(shù)a[n]，求(i, j),i f(j, n, a[j])。
f(lhs, rhs, x)指在{ [lhs, rhs]范圍中，a[k]的值=x }的數(shù)量。
分析：
很明顯：
1. f(1, i, a[i])就是指a[i]前面包括a[i]的數(shù)中，有幾個(gè)值=a[i]。
2. f(j, n, a[j])就是指a[j]后面包括a[j]的數(shù)中有幾個(gè)值=a[j]。
雖然a[x]范圍不小，但是n的范圍是1000，不是很大，所以我們可以用map預(yù)處理出f(1, i, a[i])和f(j, n, a[j])，記為s1[n], s2[n]。
這樣就變成求滿足s1[i] > s[j]， i < j情況的數(shù)量了,你會(huì)發(fā)現(xiàn)跟求逆序?qū)σ粯恿?。這時(shí)就可以用線段樹(shù)或樹(shù)狀數(shù)組求逆序數(shù)對(duì)的方法解決這個(gè)問(wèn)題了。不懂線段樹(shù)怎么解的可以看：HDU 1394 Minimum Inversion Number（線段樹(shù)求最小逆序數(shù)對(duì)）。
代碼：
/** Author: illuz * File: D.cpp* Create Date: 2014-08-16 00:18:08* Descripton: */#include #include #include #include #include
E - Pashmak and Graph
題意：
給出一個(gè)有向帶權(quán)值的圖，要求出最長(zhǎng)遞增鏈路的長(zhǎng)度。也就是當(dāng)前邊的權(quán)值要大于前一條邊的。
分析：
剛開(kāi)始寫了個(gè)搜索+map記憶化，然后就TLE了QvQ...
其實(shí)可以用數(shù)組的dp來(lái)做，先對(duì)邊從小到大排序，從小到達(dá)處理，對(duì)于相同的一類邊，進(jìn)行對(duì)邊dp，然后更新對(duì)點(diǎn)dp。
@barty巨巨：
將所有邊按邊權(quán)從小到大排序，順序掃描，如果沒(méi)有重復(fù)邊權(quán)的話，對(duì)于(u, v, d)這條有向邊，可以直接用之前求的到u點(diǎn)的最長(zhǎng)路徑+1來(lái)更新到v的最長(zhǎng)路徑。
不過(guò)題目中沒(méi)有保證所有邊權(quán)不同，為了保證嚴(yán)格遞增，所以對(duì)于相同邊權(quán)需要做一個(gè)緩沖處理。
代碼：
/** Author: illuz * Blog: http://blog.csdn.net/hcbbt* File: E.cpp* Create Date: 2014-08-16 09:43:59* Descripton: */#include #include #include #include using namespace std;#define repf(i,a,b) for(int i=(a);i<=(b);i++)const int N = 3e5 + 10;struct Edge { int x; int y; int w; bool operator <(const Edge& e) const { return w < e.w; }} e[N];int n, m;int edge[N], node[N]; // edges and nodes' dpint main() { while (~scanf("%d%d", &n, &m)) { memset(edge, 0, sizeof(edge)); memset(node, 0, sizeof(node)); repf (i, 1, m) { scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w); } sort(e + 1, e + m + 1); repf (i, 1, m) { int j = i; while (j <= m && e[i].w == e[j].w) { // update edges' dp int x = e[j].x; edge[j] = max(edge[j], node[x] + 1); j++; } j = i; while (j <= m && e[i].w == e[j].w) { // update nodes' dp int y = e[j].y; node[y] = max(edge[j], node[y]); j++; } i = j - 1; } int ans = 0; repf (i, 1, m) ans = max(ans, edge[i]); printf("%d\n", ans); } return 0;}
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com
