2019-02-14 10:43:38 |  0 Comments

## 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

2019-02-14 09:39:19 |  0 Comments

## 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
2019-02-13 09:33:40 |  0 Comments

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

2019-02-07 01:26:40 |  0 Comments

# 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）：

2019-02-07 01:05:31 |  0 Comments

## 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
2019-01-18 23:26:17 |  0 Comments  |  STL

# 6 个技巧，提升 C++11 的 vector 性能

Vector 就像是 C++ STL 容器的瑞士军刀。Bjarne Stoutsoup 有一句话 – “一般情况下，如果你需要容器，就用 vector”。像我们这样的普通人把这句话当作真理，只需要照样去做。然而，就像其它工具一样，vector 也只是个工具，它能提高效率，也能降低效率。

### 性能测试的搭建和方法:

• 所有测试都在我的 Surface Book 中运行，这台笔记本拥有主频 2.6Ghz 的酷睿 i7 处理器，8 GB 内存，安装了 Windows 10 操作系统并使用 VS2015 C++ 编译器编译运行。

• 我们会使用 Stopwatch。这个工具由 Kjell 创建，在 https://github.com/KjellKod/Stopwatch 可以找到。

• 我们会运行每个测试 100 次，然后计算平均运行时间来作为依据。运行测试的代码在这里。你可以自由下载，用于在你自己的系统中评估 vector 的性能。那里提供的代码段只反映了一次循环，这让事件变得简单。

• 我们在 vector 中存入 TestStruct 结构的数据，并使用 FillVector() 来填充 vector。它们的定义如下。

// Test struct to be inserted/removed from vector
struct BigTestStruct
{
int iValue = 1;
float fValue;
long lValue;
double dValue;
char cNameArr[10];
int iValArr[100];
};
// Helper function to populate the test vectors
void FillVector(vector<BigTestStruct>& testVector)
{
for (int i = 0; i < 10000; i++)
{
BigTestStruct bt;
testVect
Title - Artist
0:00