## Description

MZL is an active girl who has her own country.

Her big country has N cities numbered from 1 to N.She has controled the country for so long and she only remebered that there was a big earthquake M years ago,which made all the roads between the cities destroyed and all the city became broken.She also remebered that exactly one of the following things happened every recent M years:

1.She rebuild some cities that are connected with X directly and indirectly.Notice that if a city was rebuilt that it will never be broken again.

2.There is a bidirectional road between city X and city Y built.

3.There is a earthquake happened and some roads were destroyed.

She forgot the exactly cities that were rebuilt,but she only knew that no more than K cities were rebuilt in one year.Now she only want to know the maximal number of cities that could be rebuilt.At the same time she want you to tell her the smallest lexicographically plan under the best answer.Notice that 8 2 1 is smaller than 10 0 1.

## Description

Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.
Unfortunately, Dumb Zhang masters the art of becoming invisible(奇门遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb

## Sample Input

6 9
1 2 2
1 3 2
2 3 3
3 4 3
1 5 1
2 6 3
4 5 4
4 6 7
5 6 6
1 3
2 3
3 4
4 5
4 6

## Sample Output

8

【样例说明】 边(4,6)的权由7修改为3，代价为4

## HINT

1<=n<=50,1<=m<=800,1<=wi<=1000
n-->点数..m-->边数..wi--->边权

## 题解

widiwj+djwi−di≤wj+dj

wiwjdi+djwi−wj≤di+dj

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int N=1005,M=2e5

B - A <= c     (1)
C - B <= a     (2)
C - A <= b     (3)
如果要求C-A的最大值，可以知道max（C-A）= min(b,a+c),而这正对应了下图中C到A的最短路。

http://www.cnblogs.com/g0feng/archive/2012/09/13/2683880.html

# 2-SAT问题

2-SAT问题一般会给出n个布尔变量（取0或1），再给出m个限制条件，求问是否能够找到可行性解满足这些约束条件。

## 约束条件建图方式

1.必选${x}_{i}$$x_i$:从${i}^{\prime }$$i'$$i$$i$连一条有向边，表示推出${i}^{\prime }$$i'$为1是必然推出$i$$i$为1，保证${x}_{i}$$x_i$=true。
2.必不选${x}_{i}$$x_i$：从${i}^{\prime }$$i'$$i$$i$连一条有向边。
3.${x}_{i}$$x_i$${x}_{j}$$x_j$中至少选一个（${x}_{i}$$x_i$ or ${x}_{j}$$x_j$ = 1）：连接边${j}^{\prime }$$j'$->$i$$i$,${i}^{\prime }$$i'$->$j$$j$
4.${x}_{i}$$x_i$${x}_{j}$$x_j$中不能都选（${x}_{i}$$x_i$ and ${x}_{j}$$x_j$ = 0）：连接边$j$$j$->${i}^{\prime }$$i'$,$i$$i$->${j}^{\prime }$$j'$
5.${x}_{i}$$x_i$${x}_{j}$$x_j$选择情况相同（${x}_{i}$$x_i$ xor ${x}_{j}$$x_j$ = 0）：

6.${x}_{i}$$x_i$${x}_{j}$$x_j$选择情况相反（${x}_{i}$$x_i$ xor ${x}_{j}$$x_j$ = 1）：

## Description

You are given an undirected graph G = (V, E) containing N nodes and M edges. The nodes are numbered from 1 to N. A subset C of V is a vertex cover if for every edge (u, v) ∈ E, at least one of u and v belong to C. Note that C = V is always a vertex cover.
Consider a partition of V into two sets A and B. It is said to be a valid partition, if the following two conditions are satisfied: A should be a vertex cover. And for each i such that 1 ≤ i ≤ n/2, nodes 2i and 2i - 1 don't belong to the same set (i.e. one belongs to set A and the other to set B).
Determine if a valid partition exists. If it exists, provide an example of one valid partition.

## Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and M denoting the number of nodes and number of edges in the graph respectively.
Each of the following M lines contains two space-se

2019-02-05 23:39:44 |  0 Comments  |  DP

# Description

You are given array ai of length n. You may consecutively apply two operations to this array:
·remove some subsegment (continuous subsequence) of length m < n and pay for it m·a coins;
·change some elements of the array by at most 1, and pay b coins for each change.
Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.
Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.

## Input

The first line of the input contains integers n, a and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — the length of the array, the cost of removing a single element in the first operation and the cost of changing an element, respectively.
The second line contains n integers ai (2 ≤ a_i

2019-02-05 23:39:39 |  0 Comments  |  A* 贪心

# Description

Piegirl found the red button. You have one last chance to change the inevitable end.
The circuit under the button consists of n nodes, numbered from 0 to n - 1. In order to deactivate the button, the n nodes must be disarmed in a particular order. Node 0 must be disarmed first. After disarming node i, the next node to be disarmed must be either node (2·i) modulo n or node (2·i) + 1 modulo n. The last node to be disarmed must be node 0. Node 0 must be disarmed twice, but all other nodes must be disarmed exactly once.
Your task is to find any such order and print it. If there is no such order, print -1.

## Input

Input consists of a single integer n (2 ≤ n ≤ 105).

## Output

Print an order in which you can to disarm all nodes. If it is impossible, print -1 instead. If there are multiple orders, print any one of them.

## Examples

### Input

2

### Output

0 1 0

### Input

3

### Output

-1

### Input

4

### Output

0 1 3 2 0

### Input

16

### Output

0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0

## 题目大意

2019-02-03 22:46:55 |  0 Comments  |  三分

# 三分法

(图片转自chenxiaoran666的博客)

# 示例代码

int find(int l,int r){
if(l >= r)return l;
int midl = (l+r) >> 1;
int midr = (midl + r) >> 1;
if(a[midl] > a[midr])
return find(l,midr);
else return find(midl,r);
}﻿​

while(l < r){
int midl = (l + r) >> 1;
int midr = (midl + r) >> 1;
if(a[midl] > a[midr])
r = midr;
else l = midl;
}﻿​

2019-01-27 22:31:09 |  0 Comments  |  DP

## 数位DP

emmm……

nope！ 如果是a，b的范围是1 <= a,b <= 20000000000呢？你还暴力拆开检查么？你家计算机跑上一天都不一定能跑出来。

void init(){
memset(dp,0,sizeof(dp));
for(int i = 0;i <= 9;++i)
dp[1][i] = 1;
for(int i = 2;i <= 10;++i)
for(int j = 0;j <= 9;++j)
for(int k = 0;k <= 9;++k){
if(满足题目条件)
dp[i][j] += dp[i-1][k];
}
return;
}

long long solve(long long x){
long long ans = 0;
k = 0;
memset(m,0,sizeof(m
Title - Artist
0:00