题目大意

两个人从家里出发，Panda比Sheep晚走x分钟，在地铁上两人保持m次通信，每次通信Panda在a和b之间，Sheep在c和d之间。到终点后，求问每两站之间所需要的时间是多少，如果无法计算输出IMPOSSIBLE

题解

我们可以在草稿纸上画画图，把两人的位置之间连线，标记上表示这一段的时间为x。

然后我们可以看到两者区间两端点的关系，进行分类讨论：

如果a = b：

1.c = d 那么就是c - a = x，也就是c - a <= x, c - a >= x,也即 c - a  <= x,a - c <= -x;

2.c ≠ d 则c - a < x,d - a > x，也即c - a  <= x-1，a - d <= -x-1;

如果a ≠ b：

1. c = d 那么就是 c - a > x,c - b < x,也即a - c <= -x-1,c - b <= x-1;

2. c ≠ d 那么就是c - b < x,d - a > x，也即c - b <= x - 1,a - d <= -x-1;

根据这些关系很容易就能想到此题是一个差分约束系统。只需要用SPFA求解就行了。

IMPOSSIBLE的情况就是出现负环或者正环（看自己怎么定义边了，要注意SPFA中的更新的不等号方向要和建边一致，不然会WA）。

非IMPOSSIBLE的情况，两站之间的距离就是dis[i] - dis[i-1]（标程里面写的是最长路，所以也就是非正环情况）。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 2005;
typedef long long ll;
struct edge{
    int to,next;
    ll dis;
}e[maxn<<5];
int cnt = 0;
int t;
int h[maxn];
int a,b,c,d;
int n,m;
ll x;
void add(int u,int v,int d){
    e[cnt].to = v;e[cnt].next = h

题目大意

求以任意点为起点的长度为k的路径的距离的最大值，如果没有这样的路径输出impossible。

题解

Nanjing University的同学们在写题解的时候真的是高估了我的英文水平……看了两个小时才看懂这个题……

那么这篇就相当于把Nanjing University的同学们的英文题解翻译一遍搬过来。

首先，这种题目是一种典型的模型。

这种题有两种做法，一种是分别固定起点，然后不断地跑bfs。不过这种方法可能不适合这种数据范围。

那么介绍第二种做法，color coding。

简单来说，就是对每个点进行随机染色，之后用状压DP的思想，求出dp[v][sum]，表示以v为中止点，sum为当前走过的颜色的的二进制位表示（注意不能走同颜色的点）时的距离的最大值。

于是我们就是需要统计dp[1...n][(1<<k)-1]中的最大值作为我们的答案。这样做时间复杂度是O（2^km）的

不过很明显这样的做法是并不一定能够正确的，因为很有可能我们把本应成为答案的部分中的点随机成为颜色相同的点，从而不能够同时去走。

所以说color coding实际上是一种具有成功概率性的思路。最优路径上的点的颜色全部是不同的概率为k!/k^k,所以我们期望做k^k/k！次这样的过程，就有较大概率能够算出最优答案。

通过多次测试，color coding这样的思路就可以不断逼近正确答案。

最终此题的复杂度就是做一次的复杂度乘做的次数。

By the way，我在hdu上交的时候运行300次就T了，而运行200次可以AC，题解代码给的是250次。。。看起来这个还是有点看脸的？

代码

#include <bits/stdc++.h>
using namespace std;
int t,n,m,k;
const int maxn = 2e4+5;
struct edge{
    int to,next,dis;
}e[maxn<<1];
int h[maxn];
int dp[maxn][70];
int cnt = 0;
void add(int u,int v,int d){
    e[cnt].to = v;e[cnt].dis = d;e[cnt].next = h[u];
    h[u] = cnt++;
    return;
}
int u,v,w;
int color[maxn];
int work(){

题目大意

先手有n张牌，后手有m张牌，如果某人打出了某种颜色的牌，那么另一个人就不能打这种颜色的牌，最后不能出牌的人输。求问是先手胜还是后手胜。

题解

两人都是按最优策略取的博弈，不过和SG函数并没有什么关系。

两个人肯定每回合都是贪心的取对自己最有利的方案。

首先我们将两人都有的颜色的牌抽出来，剩下的就是两人各自独立的牌集，不会受对方出牌的影响。

然后我们考虑被抽出来的牌，怎样取能使得局面变得对自己有利。

如果对于某种颜色，两人共有的这种颜色的牌比较大，那么当前的出牌者选择出这种颜色的牌的优先级肯定就更高。

然后当前的人出一种颜色的牌，就可以看成是把自己原有的这种颜色的牌全部收回，把对方原有的这种颜色的牌全部丢掉。

所以我们需要离散化颜色，然后对于公共颜色的牌全部抽出，然后按照两人手中的这种颜色的牌的总数从大到小排序，然后让先手先选，后手后选直到全部选完。

选完后我们比较一下两人手里的牌的总数。

如果先手手中的牌比后手多，则先手必胜，否则先手必败。

（对于我取消流同步的cin比自己写的快读要快这件事，我真的很疑惑……）

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int maxn = 1e5+5;
int a[maxn],b[maxn];
unsigned long long mod;
unsigned long long k1, k2;
unsigned long long rng() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}
int t;
int n,m,p;
int cnt = 0;
int c[maxn<<1];
int q[maxn<<1];
int com[maxn<<1];
struct point{
    int val,id;
}e[maxn];
bool cmp(point a,point b

题目大意

一场考试有n个题目，总共为m分，如果要通过一个分值为x的题目，需要复习x+1小时。

现在目标为通过至少k个题目，求问至少要复习多长时间。

题解

首先我们从出题老师的角度来看，怎么样才能让考生无法通过考试呢。

当然是让学生复习时间最少的n-k+1门科目不能通过考试，也就是要求让他们的复习时间恰好等于复习分数。

然后镜头转回学生，我们需要复习时间最少的n-k+1门复习时间最少的科目中有1门能通过就好了。

所以最后的答案是(m/(n-k+1)+1) *(k-1)+m+1.

代码

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
int T;
ll n, m, k;
int main(){
    scanf("%d", &T);
    while (T--){
        scanf("%lld%lld%lld", &n, &m, &k);
        ll p = m / (n - k + 1) + 1;
        ll ans = p * (k-1) + m + 1;
        printf("%lld\n",ans);
    }
    return 0;
} 

题目大意

 给你一个数字串，问你如果一步只能跳i或j（0≤i,j≤9）的话，跳到x‘ % 10，需要至少添加多少数字进入这个串中，使得添加数字后的串是可能通过每次跳i或者j构造出来的。

题解

这绝对算一个好题。

首先我们看这个跳法，每一次跳都只能跳到当前数+x 对10取模，所以相当于我们在10的完全剩余系里面疯狂跳。

然后注意到其实我们从当前数要跳到数字串中的下一个数的时候，数字串每两个数之间的跳法是互不影响的。于是我们对于数字串每两个数之间也就是求最短路处理。

我们设mp[i][j][x][y]表示从x跳到y，只能一次性跳i或者j的最短距离，然后对于10×10的方阵，直接用Floyd预处理出来。

然后我们进入数字串直接扫一遍，如果下一个与当前位置最短路为INF，直接输出-1，否则答案就加上两个之间的最短距离-1.

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
string s;
int len = 0;
int mp[10][10][10][10];
long long ans = 0;
int main(){
    for(int i = 0;i <= 9;++i){
        for(int j = 0;j <= 9;++j){
            for(int k = 0;k <= 9;++k){
                for(int l = 0;l <= 9;++l){
                    mp[i][j][k][l] = INF;
                }
            }
        }
    }
    for(int i = 0;i <= 9;++i){
        for(int j = 0;j <= 9;++j){
            for(int k = 0;k <= 9;++k){
//                if(i != 0)
                    mp[i][j][k][(k+i)%10] = 1;
//                if(j != 0)
                    mp[i][j][k][(k+j)%10] = 1;
   

题目大意

给n个数，每个时刻就会有一个新的数可用，求每个时刻所有可用的数字按照序列位置组成的最长上升子序列长度。数据生成完全随机。

题解

由于数据完全随机生成，所以当所有数都可用的时候，LIS的期望长度是n^1/2 。我们删掉一个数，这个数在LIS中的概率期望是1/n^1/2。

我们可以把原问题逆向来考虑，从一开始所有数可用，然后不断删除数字。

如果删除的数字在上一次的LIS中，则我们需要重新求一次LIS，否则就延续上一次的答案。

如果我们使用O(nlogn)方法的LIS，那么一组数据的总体时间复杂度就是O(n^3/2logn)

这题因为手写二分写丑了没用lower_bound被卡T一次，然后因为行末空格被卡PE一次，AWSL。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 50005;
int T;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
int n;
int p[maxn],k[maxn],seq[maxn];
int ans[maxn],vis[maxn],ban[maxn],pre[maxn];
int len = 0;
int pos;
int work(){
    for(int i = 1;i <= len;++i)
        seq[i] = 0,vis[seq[i]] = 0;
    seq[0] = 0;
    len = 0;
    f

There is an array of length N consisting of non-negative integers. The array is sorted in non-decreasing order. Each number in the array appears exactly K times, except one element, which appears at least once, but less than K times. Your task is to identify that element.

This is an interactive problem. You are only given the integer N in the input. Both the array and the value of K are hidden. You are allowed to ask the judge the following queries: What is the value of the element at index i of the array? Identify the value of the element with frequency less than K by asking at most 60 such queries.

Input and Output

The first line of the input contains a single integer T denoting the number of test cases.

For each test case, you should start by reading a single line containing one integer N from the input.

You can interact with the judge using the standard input and output. There are two types of operations: to perform one operation, you should print to the standard output a line containin

题目大意

平面直角坐标系上有n个点，每个点有wi的价值，你可以选出一个矩形，获得矩形内部和边界上所有点的价值总和，求问最大的价值总和是多少。

题解

一开始一看，这题简单啊，直接离散化上二维前缀和好了。

然后写着写着发现不对劲，二维前缀和枚举是O(n^4)的。。。

然后后面想到了其实也就是离散化后维护最大子矩阵和，大概是要用二维线段树维护的……不过这个代码难度和复杂度就……

最后是队友给了思路：把问题通过一系列手法降维处理，把最大子段和转化为最大子区间和，这样就可以用一维的普通线段树去维护了。

首先还是要离散化，然后对于所有点按离散化后的x坐标从小到大排序。

然后我们枚举一个左侧的边界作为起始，枚举右侧边界作为终止，建立一棵投影到y轴上的线段树，把我们枚举的两个边界及其中间的所有点全部投影到y轴，并加入线段树进行单点修改，维护线段树区间最大子段和，这样我们枚举的两个边界中所维护的线段树的最大子段和就是以这两条边为边界的最大子矩阵和。

由于点数比较少，所以每枚举一次左侧边界后面的操作都是复杂度O(nlogn)的。所以对于每一个case，我们这个解决方案的总复杂度就是O(n²logn)的

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans = 0;
int T;
int n;
const int maxn = 2e5+5;
struct point{
    int x,y;
    ll w;
}p[maxn];
int xx[maxn],yy[maxn];
int tot1,tot2;
struct tree{
    int l,r;
    ll sum,mxl,mxr,mxs;
}tr[maxn<<2];
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        

 Description

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为 Master。除了 Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者 发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递 人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。写一个程序，给定每一个忍者 i的上级 Bi，薪水Ci，领导力L i，以及支付给忍者们的薪水总预算 M，输出在预算内满足上述要求时顾客满意度的最大值。

Input

Output

输出一个数，表示在预算内顾客的满意度的最大值。

Sample Input

5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

Sample Output

6

数据范围

题解

 我们将关系树图建出来，直接dfs，对于每一个点维护一个大根堆、子树中选取忍者的个数，大根堆用左偏树的方法实现合并。

对于当前的管理者，计算其子树的选中的忍者的总共需要的薪水sum，如果sum

题目大意

给出两个长度为n的序列a，b,重新排列a、b使得两个序列各个位置上的数异或起来得到的序列C字典序最小，并输出最小字典序的c

题解

这题思路甚为巧妙。

关于异或的题目，我们总是分为各个二进制位置上的0/1来看，例如线性基、0/1Trie。此题就是通过0/1Trie来实现的。

首先我们对于两个序列，建立两个0/1Trie。

然后我们首先从第一个Trie中找出一个数，放入当前的候选答案的栈内，之后去另外一棵Trie中找与之异或值最小的数，再放入栈中，再去当前找到的值所在Trie的另一棵Trie中找与之异或值最小的数放入栈中，如此往复。

直到我们找到一个长度为2的环，此时这个长度为2的环中的两个数就是c中的一组答案了。因为他们两个相互为异或的最小值。就把他们存入c，并且从栈中pop掉，并将这两个数在自己的Trie树中删除，继续循环上面的步骤。

按照这种方法，直到我们把所有n个异或值都找出来，后面只需要排一遍序就是我们需要的最终答案了。

至于为什么环的长度一定为2而不可能为更多，这个东西是有证明的，不过暂时还没理解，暂时不写了。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+10;
int ch[maxn*32][2],cnt[maxn*32][2];
int n,T;
int v,c[maxn];
int tot = 0