111qqz

1968: [Ahoi2005]COMMON 约数研究 # Time Limit: 1 Sec Memory Limit: 64 MB Submit: 1997 Solved: 1508 [Submit][Status][Discuss] Description # Input # 只有一行一个整数 N（0 < N < 1000000）。

2463: [中山市选2009]谁能赢呢？ # Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1826 Solved: 1347 [Submit][Status][Discuss] Description # 小明和小红经常玩一个博弈游戏。给定一个n×n的棋盘，一个石头被放在棋盘的左上角。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？

题目链接 题意： # For every pair of triplets, Ta = (Ia, Ja, Ka) and T__b = (Ib, Jb, Kb), we define the difference value between Ta and_T__b_ as follows: D(Ta,_ Tb_) = max {Ia − Ib, Ja − Jb, Ka − Kb} − min {Ia − Ib, Ja − Jb, Ka − Kb}

poj 2443题目链接 题意：给出n个可重集…以及集合中的元素。。。现在若干查询，每个查询给出一对数x,y，询问是否存在某个集合，同时拥有x,y两个元素（x,y可以相同）

题目链接 题意：容量为V的背包，n个骨头，给出价值和体积，问最多能装多少价值的背包。 思路：01背包裸体。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年11月16日 星期三 15时14分36秒 4File Name :code/hdu/2602.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=1E3+7; 34int dp[N],value[N],cost[N]; 35int n,V; 36void solve(int v,int c) 37{ 38 for ( int i = V; i >= c; i --) 39 dp[i] = max(dp[i],dp[i-c]+v); 40} 41int main() 42{ 43 #ifndef ONLINE_JUDGE 44 freopen("code/in.txt","r",stdin); 45 #endif 46 int T; 47 cin>>T; 48 while (T--) 49 { 50 scanf("%d%d",&n,&V); 51 ms(dp,0); 52 for ( int i = 1 ;i <= n ; i++) scanf("%d",&value[i]); 53 for ( int i = 1; i <= n ; i++) scanf("%d",&cost[i]); 54 for ( int i = 1 ; i <= n ; i++) solve(value[i],cost[i]); 55 int ans = 0 ; 56 57 for ( int i = 0 ; i <= V ; i++) ans = max(ans,dp[i]); 58 printf("%d\n",ans); 59 } 60 61 #ifndef ONLINE_JUDGE 62 fclose(stdin); 63 #endif 64 return 0; 65}

hdu1864题目链接 题意：中文题目，不多说了。 思路：正解是01背包，呵呵呵。 出题人是傻逼吗？ 不给数据范围？ 以及，正解的01背包基于所有的发票额度的只有2位小数。这是让人猜？ 本来看到这题这么恶心时不打算写的…

题目链接 题意： 给出n个银行 ，以及抢劫每个银行可以得到的价值和被抓的概率，不同银行之间被抓的概率是相互独立的，现在给出安全概率p，只有当概率从小于安全概率时才是安全的，问最多能抢劫多少价值。

题目链接 题意：给出n(n<=1E3)个字符，字符可能为’D’,‘I’,’?’，第i位对应的字符分别表示，第i位大于第i+1位，第i位小于第i+1位，或者不确定。

题目链接 题意：问长度为n的“波浪”型排列（即1..n每个数出现一次）有多少。波浪型的含义是，“高低高”或者“低高低” 思路：我们考虑当前已经知道i-1个数的波浪型的排列的方案数，那么当第i个数到来时，第i个数一定是最大的。

题目链接 题意：给出n(n<=200000)个数，问所有区间[l,r]中mex的和。 （一个区间mex的定义为，这个区间中没有出现的最小的非负数） 思路：我们观察到mex(1,i)随着i增大，是不减的。(单调是线段树查询区间的时候非常好用的东西，这也是此题的突破口)