Rumah > Artikel > pangkalan data > 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。 代码 :
ACM
题目地址:Codeforces Round #261 (Div. 2)
题意:
一个正方形,它的边平行于坐标轴,给出这个正方形的两个点,求出另外两个点。
分析:
判断下是否平行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>