技术归档

http://codeforces.com/contest/29/problem/C 题意：给出n个边的关系，保证可以构成一条链。正向或者反向输出这个链。 思路：由于下标很大(1E9)，而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e;即可。然后找到一个度为1的点。。做个dfs…

http://codeforces.com/problemset/problem/31/C 题意：给出n个借用教室的时间安排，可能会有冲突。要求恰好去掉一个时间安排使得剩下的时间安排不冲突。问多多少种方案。 思路：首先一个直觉是。。除非初始就没有任何冲突。。不然这个答案不会很大。。

http://codeforces.com/contest/27/problem/C 题意：给出一个序列，问是否存在一个disordered的子序列。。输出长度并输出组成子序列的下表（1..n）。如果有多组，输出任意一组。 disordered的意思是。。升序或者降序（不严格也可以)之外的情况。 思路： 首先我们可以知道，我们要找的子序列至少需要三个点。因为两个点怎么看都是有序的。而如果有k个点（k>3）组成的子序列存在。。那么机智得去掉其中一些点，可以只剩三个 ，同样满足题意。所以我们只需要找到三个点即可。如果把点以下标为横坐标，值为纵坐标花在坐标系上，就是找一个v型或者倒v型的三个点。

http://codeforces.com/contest/30/problem/C 题意：给出n个target在一个二维平面上。给出每个target的坐标，出现的时间，以及击中的概率。target出现之后就会瞬间消失，枪移动的单位速度为1，射击不需要时间。问能击中的target的最大期望是多少。

http://codeforces.com/problemset/problem/14/C 题意：给出四条边的坐标，问能否形成一个边与坐标轴平行的矩形。边可能退化成点。 思路：首先第一步，检查有没有边退化成点以及是否有不平行的边。

http://codeforces.com/contest/18/problem/C 题意：将一个序列分成两个非空的部分，保证和相等，问有多少种方法。 思路：做过一个三部分的。。。两部分直接一个前缀和就好了把。。。有一个需要注意的是。。判断负数是否是奇数的时候需要加个绝对值。。。

http://codeforces.com/contest/12/problem/C 题意：有n个价格价格，m个要买的东西（可能有相同的种类，设为k种），把n个标签中拿出k个给个贴上。。。问最大价钱和最少价钱分别是多少。 思路：贪心。不过要按照map的value排序。。然后发现其实不用排序。。因为map的key值其实不影响。

http://codeforces.com/contest/16/problem/C 题意：给定长宽a,b和分辨率x:y,注意分辨率x:y未必是最简比。问将现有的size裁剪成比例为x:y，使得面积最大的长宽是多少。 思路：可以通过找 x,y能扩大的倍数为k，找到一个最大的k使得k*x<=a&&k;*y<=b。可以二分搞，但其实也可以不用。能扩大的最大的倍数其实就是 min(a/x,b/y). ps:收获了gcd更简单的一种写法。 直接 return b?gcd(b,a%b):a;

1gconftool-2 --set --type=list --list-type=string /apps/gedit-2/preferences/encodings/auto_detected "[UTF-8,CURRENT,GB18030,ISO-8859-15,UTF-16]"

Open up the Terminal (Alt + F2 > Terminal). Remove OpenJDK installation. 1sudo apt-get update && apt-get remove openjdk* Download Oracle JDK from here. You are looking for a linux version with tar.gz extension. Also choose the right version from 32-bit (x86) and 64bit (x64) one.

http://codeforces.com/contest/612/problem/C 题意：其实就是栈的基本操作。。水题。 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月25日 星期五 22时58分50秒 4File Name :code/cf/edu4/C.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E6+7; 34int len; 35char st[N]; 36int cost = 0 ; 37 38char a[N]; 39int n ; 40 41 42int which(char ch) 43{ 44 if (ch=='<'||ch=='{'||ch=='('||ch=='[') return 1; 45 return 2; 46} 47int kin(char ch) 48{ 49 if (ch=='{'||ch=='}') return 1; 50 if (ch=='['||ch==']') return 2; 51 if (ch=='<'||ch=='>') return 3; 52 if (ch=='('||ch==')') return 4; 53} 54bool ok(char x,char y) 55{ 56 int res = 0 ; 57 if(x=='<'||x=='{'||x=='['||x=='(') res++; 58 if (y=='>'||y=='}'||y==']'||y==')') res++; 59 if (res==2) 60 { 61 if (kin(x)!=kin(y)) cost++; 62// cout<<"x:"<<x<<" y:"<<y<<endl; 63 return true; 64 } 65 return false; 66} 67 68int main() 69{ 70 #ifndef ONLINE_JUDGE 71 freopen("code/in.txt","r",stdin); 72 #endif 73 cin>>st; 74 len = strlen(st); 75 int head = -1; 76 int ans = 0 ; 77 78 for ( int i = 0 ; i < len ; i++) 79 { 80 if (head==-1) 81 { 82 head++; 83 a[head] = st[i]; 84 if (which(st[i])==2) 85 { 86 puts("Impossible"); 87 return 0; 88 } 89 90 continue; 91 } 92 if (ok(a[head],st[i])) 93 { 94 head--; 95 } 96 else 97 { 98 head++; 99 a[head] = st[i]; 100 } 101 102// cout<<"head:"<<head<<endl; 103 } 104// cout<<"head:"<<head<<endl; 105 if (head!=-1) 106 { 107 puts("Impossible"); 108 } 109 else 110 { 111 cout<<cost<<endl; 112 } 113 114 #ifndef ONLINE_JUDGE 115 fclose(stdin); 116 #endif 117 return 0; 118}

http://codeforces.com/contest/612/problem/B 水。 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月25日 星期五 22时58分38秒 4File Name :code/cf/edu4/B.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=2E5+7; 34int n; 35struct node 36{ 37 int val; 38 int id; 39 40 bool operator <(node b)const 41 { 42 return val<b.val; 43 } 44}q[N]; 45int main() 46{ 47 #ifndef ONLINE_JUDGE 48 freopen("code/in.txt","r",stdin); 49 #endif 50 cin>>n; 51 for ( int i = 1 ; i <= n ; i++ ) 52 { 53 scanf("%d",&q[i].val); 54 q[i].id = i; 55 } 56 sort(q+1,q+n+1); 57 LL ans = 0 ; 58 q[0].id = 0 ; 59 for ( int i = 1 ; i <= n-1 ; i++) 60 { 61 ans += LL (abs(q[i+1].id-q[i].id)); 62 } 63 cout<<ans<<endl; 64 65 #ifndef ONLINE_JUDGE 66 fclose(stdin); 67 #endif 68 return 0; 69}

http://codeforces.com/contest/612/problem/A 水题…直接枚举就好。 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月25日 星期五 22时58分26秒 4File Name :code/cf/edu4/A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=105; 34int n,p,q; 35char st[N]; 36bool v[10005]; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 cin>>n>>p>>q; 43 cin>>st; 44 ms(v,false); 45 int b,c; 46 for ( int i = 0 ; i*p<=105 ; i++ ) 47 { 48 for ( int j = 0 ; j*q <= 105 ; j++) 49 { 50 v[i*p+j*q] = true; 51 if (i*p+j*q==n) 52 { 53 b = i; 54 c = j; 55 } 56 } 57 } 58// cout<<"b:"<<b<<endl; 59// cout<<"c:"<<c<<endl; 60 if (!v[n]) 61 { 62 puts("-1"); 63 } 64 else 65 { 66 int cnt = 0 ; 67 printf("%d\n",b+c); 68 for ( int i = 1 ; i <= b ; i++) 69 { 70 for ( int i = 0 ; i < p ; i++) 71 printf("%c",st[cnt]),cnt++; 72 printf("\n"); 73 } 74 for ( int i =1 ; i <= c ; i++) 75 { 76 for ( int i = 0 ; i < q ; i++) 77 printf("%c",st[cnt]),cnt++; 78 printf("\n"); 79 } 80 } 81 82 83 84 #ifndef ONLINE_JUDGE 85 fclose(stdin); 86 #endif 87 return 0; 88}

http://codeforces.com/contest/612/problem/D 题意：给出n个线段信息，每个线段以l,r的形式给出。给定k。要求从作到右给出至少有k个线段覆盖的区间的信息。并使得区间数目尽可能少。

http://codeforces.com/contest/327/problem/A 题意：给定一段序列，只由0,1组成。要求选一段非空区间，做翻转操作（0变1,1变0），问变完之后1最多能有多少。 思路：最后的1个个数=初始的1的个数+变换区间的0的个数-变换区间的1的个数。初始的是常数。那么我们只要找到某一个区间内，0的个数-1的个数有最大值即可。如果a[i]==0的时候令b[i]=1，否则b[i]=0,那就是经典了最大连续区间和的问题了。dp的思想o(n)可以解决。

http://codeforces.com/contest/456/problem/C 题意：给出n(1E5)个数（1E5），每次可以选一个数a[k]并删掉a[k],a[k]-1,a[k]+1得到a[k]分，问最多能得到的分数。 思路：裸dp.f[i]表示选到数i的时候能达到的最大分数。开一个计数数组cnt[x]表示数字x出现的次数。那么显然有f[0]=0,f[1]=cnt[1],f[i(i>=2)] = max(f[i-1]，f[i-2]+f[i]*cnt[i]);答案为f[max(a[i])]，注意要开long long

http://codeforces.com/contest/608/problem/B 题意：给定两个字符串a,b，问b中的每个连续的长度为a的子串与a的哈密顿距离的和是多少。哈密顿距离是对应位置的字符的差的绝对值的和。由于是01串，也就是字符不同的位置数。 思路：类似前缀和。0和1分别搞。注意开long long

http://codeforces.com/contest/608/problem/A 题意：一个电梯，从s到0层，单项，给出n个人，每个人在某时间出现在某层，问要花多长时间把所有人运到0。初始电梯在s，每下一层话费时间1，上来人不花时间。 思路：由于电梯只能是单项，那么到达某一层的时候，一定要等到把这层中最晚来的那个接走。所以排序的时候按照楼层高到低为第一关键字，等待时间长到短为第二关键字。对于同一楼层出现的，只考虑第一个即可，也就是最后出现的。需要注意的是最后接完最后一个人以后把电梯运行道0层。

http://codeforces.com/contest/599/problem/D 题意：给出总的方格数x，问有多少种不同尺寸的矩形满足题意，输出方案数和长宽（3,5和5,3算两种） 思路：比赛的时候gg了。。其实稍微在纸上推一下。就会得到对于n,m的矩形，一共会有-nnn+3nnm+n+3n*m的方格。数量级是n3。 我们可以实际跑一遍。发现对于x1E18的数量级，n不会超过1442550，1E6,可以搞。

http://codeforces.com/contest/602/problem/D 题意：见题目描述。 思路：我们很容易发现，l[h]函数其实就是在求区间斜率的最大值。哦不对，是斜率的绝对值的最大值。而且一个显而易见的结论是，斜率最大值一定是由相邻的点得到。画图可以很容易看出。