Codeforces Round #261 (Div. 2)[ABCDE]

Codeforces Round #261 (Div. 2)[ABCDE] ACM 题目地址:Codeforces Round #261 (Div. 2) A - Pashmak and Garden 题意 ： 一个正方形，它的边平行于坐标轴，给出这个正方形的两个点，求出另外两个点。 分析 ： 判断下是否平行X轴或平行Y轴，各种if。 代码 ：

Codeforces Round #261 (Div. 2)[ABCDE]

ACM

题目地址:Codeforces Round #261 (Div. 2)

A - Pashmak and Garden

题意： 
一个正方形，它的边平行于坐标轴，给出这个正方形的两个点，求出另外两个点。

分析： 
判断下是否平行X轴或平行Y轴，各种if。

代码：

/*
*  Author:      illuz <iilluzen>
*  File:        A.cpp
*  Create Date: 2014-08-15 23:35:17
*  Descripton:   
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
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 <br>
<br>

<hr>

<h2>
<span>B - Pashmak and Flowers</span>
</h2>
<p>
<span>题意</span>： <br>
在n个数中取出两个数，使得差值最大，问差值和有几种取法。 <br>
两种取法不同当且仅当：两种方法至少有一个不同位置的数。</p>
<p>
<span>分析</span>：</p>
<p>
很明显差值就是<code>最大-最小</code>。</p>
<p>
如果两个数不是相同的，那么取法就是<code>max_cnt * min_cnt</code>了。 <br>
如果相同就要注意了，因为<code>max_cnt * min_cnt</code>里面有一些取法一样的数。 <br>
比如：5 1 1 1 1 1。</p>
<ol>
<li>那么我们可以这样考虑，第一次可以取5种，第二次可以取(5-1)钟，但是这里面(i,j)和(j,i)都取过，所以得减半，所以结果就是<code>n*(n-1)/2</code>。</li>
<li>或者可以这样考虑，我们为了不要取重复，规定第一次取的位置肯定在第二次前面，如果第一次取pos1，那么下次只能取(n-1)钟；如果第一次取pos2，第二次就(n-2)....累计就是<code>(n-1)*n/2</code>了。</li>
</ol>
<p>
<span>代码</span>：</p>
<pre class="brush:php;toolbar:false">/*
*  Author:      illuz <iilluzen>
*  File:        B.cpp
*  Create Date: 2014-08-15 23:51:15
*  Descripton:   
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define repf(i,a,b) for(int i=(a);i> t) {
		repf (i, 0, t - 1) {
			cin >> a[i];
		}
		sort (a, a + t);
		if (a[0] == a[t - 1]) {
			cout = 0 && a[i] == a[t - 1])
			mmax++, i--;

		cout <br>
<br>

<hr>

<h2>
<span>C - Pashmak and Buses</span>
</h2>
<p>
<span>题意</span>： <br>
n个人坐车，有k辆车带他们去d个地方玩。问怎么安排使得这d天他们没有一对人一直在一起的（FFF团的胜利）。</p>
<p>
<span>分析</span>： <br>
相当于：d行n列，每个位置填一个1～k的整数，要求不能有两列完全一样。 <br>
爆搜过去即可，只要有解就行了。</p>
<p>
<span>代码</span>：</p>
<pre class="brush:php;toolbar:false">/*
*  Author:      illuz <iilluzen>
*  File:        C.cpp
*  Create Date: 2014-08-16 00:47:18
*  Descripton:   
*/

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using 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 <br>
<br>

<hr>

<h2>
<span>D - Pashmak and Parmida's problem</span>
</h2>
<p>
<span>题意</span>： <br>
给出一些数a[n]，求(i, j),<code>i<j>的数量，使得：<code>f(1,
 i, a[i]) > f(j, n, a[j])</code>。<br>
<code>f(lhs, rhs, x)</code>指在<code>{
 [lhs, rhs]范围中，a[k]的值=x }</code>的数量。</j></code></p>
<p>
<span>分析</span>： <br>
很明显： <br>
1. <code>f(1, i, a[i])</code>就是指a[i]前面包括a[i]的数中，有几个值=a[i]。 <br>
2. <code>f(j, n, a[j])</code>就是指a[j]后面包括a[j]的数中有几个值=a[j]。</p>
<p>
虽然a[x]范围不小，但是n的范围是1000，不是很大，所以我们可以用map预处理出<code>f(1, i, a[i])</code>和<code>f(j,
 n, a[j])</code>，记为s1[n], s2[n]。</p>
<p>
这样就变成求满足<code>s1[i] > s[j]， i 情况的数量了,你会发现跟求逆序对一样了。这时就可以用线段树或树状数组求逆序数对的方法解决这个问题了。不懂线段树怎么解的可以看：HDU
 1394 Minimum Inversion Number（线段树求最小逆序数对）。</code></p>
<p>
<span>代码</span>：</p>
<pre class="brush:php;toolbar:false">/*
*  Author:      illuz <iilluzen>
*  File:        D.cpp
*  Create Date: 2014-08-16 00:18:08
*  Descripton:   
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i=(b);i--)
typedef long long ll;
#define lson(x) ((x) > 1;
		build(l, m, lson(pos));
		build(m + 1, r, rson(pos));
		update(pos);
	}

	// add the point x with y
	void modify(int l, int r, int pos, int x, ll y) {
		if (l == r) {
			node[pos].w += y;
			return;
		}
		int m = (l + r) >> 1;
		if (x > 1;
		ll res = 0;
		if (x  m)
			res += query(m + 1, r, rson(pos), x, y);
		return res;
	}
} sgm;

ll t, a[N];
int s1[N], s2[N];

map<ll int> mp;

int main() {
	while (cin >> t) {
		mp.clear();
		rep (i, t) {
			cin >> a[i];
			mp[a[i]]++;
			s1[i] = mp[a[i]];
		}
		mp.clear();
		for (int i = t - 1; i >= 0; i--) {
			mp[a[i]]++;
			s2[i] = mp[a[i]];
		}
		sgm.build(1, t, ROOT);
		ll ans = 0;
		rep (i, t) {
			ans += sgm.query(1, t, ROOT, s2[i] + 1, t); 
			sgm.modify(1, t, ROOT, s1[i], 1);
			//cout <br>
<br>

<hr>

<h2>
<span>E - Pashmak and Graph</span>
</h2>
<p>
<span>题意</span>： <br>
给出一个有向带权值的图，要求出最长递增链路的长度。也就是当前边的权值要大于前一条边的。</p>
<p>
<span>分析</span>： <br>
刚开始写了个搜索+map记忆化，然后就TLE了QvQ... <br>
其实可以用数组的dp来做，先对边从小到大排序，从小到达处理，对于相同的一类边，进行对边dp，然后更新对点dp。</p>
<p>
@barty巨巨：</p>
<blockquote>
<p>将所有边按边权从小到大排序，顺序扫描，如果没有重复边权的话，对于(u, v, d)这条有向边，可以直接用之前求的到u点的最长路径+1来更新到v的最长路径。 <br>
不过题目中没有保证所有边权不同，为了保证严格递增，所以对于相同边权需要做一个缓冲处理。</p>
</blockquote>
<p>
<span>代码</span>：</p>
<pre class="brush:php;toolbar:false">/*
*  Author:      illuz <iilluzen>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        E.cpp
*  Create Date: 2014-08-16 09:43:59
*  Descripton:   
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<br>
<br>

<p><br>
</p>


</algorithm></cstring></cstdio></iostream></iilluzen>