这道题两次二分，相当经典。首先我们知道，A^i可以二分求出。
然后我们需要对整个题目的数据规模k进行二分。
比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) 应用这个式子后，规模k减小了一半。
我们二分求即可得到原问题的答案。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,m;
struct mitrix
{
int a[31][3...
阅读全文
传送门
其他不讲，就说说建图吧，下面以3个点为例：
我用的算法效率不高，想更快的可以用dinic或sap
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,en;
int f[41111];
int fst[333],next[41111],node[41111],c[41111],lu[333],pre[333];
double l[41111];
double x[333],y[333],z[333];
int jj[333],cc[333];
bool vis[333];
int q[33333];
...
阅读全文
思路：首先做个预处理，把每一行可以放的状态存起来，以后就可以只看这么多状态而不是for全看一遍了。
之后，因为放一个可以影响四个方向2格，所以第i行的状态和i-1行i-2行有关系的，通过之前的状态来推，状态转移方程可以写为：
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+f[i][j])
这里i代表第i行，j为第i行的状态，k为第i-1行状态，l为i-2行状态，f[i][j]表示第i行在j状态下放的个数。
记得前两行特殊处理下。
这里直接开...
阅读全文
思路：网上说是Havel-Hakimi定理，不管他什么定理，反正和我的思路一样(呵呵呵。）就是每次将剩下的排序，找度数最大的，与其他中较大的几个建边，如果和剩下的都建了，这个点还有度数剩余，那么肯定不能构图了。否则一直这样构造。
之后关于判断有没有多种不同的图，我的思路是这样的，找到这样的V1，V2，V3，V4四个点，是的它们符合如下条件，v1与v2有边，v3和v4有边，v1与v4没边，v3和v2没边，如果找到了这样的四个点，那么...
阅读全文
A positive number y is called magic number if for every positive integerx it satisfies that puty to the right ofx, which will form a new integerz,
z mod y = 0.
Input
The input has multiple cases, each case contains two positve integers m,n(1 <=m <=n <= 2^31-1), proceed to the end of file.
Output
For each case, output the total number of magic numbers between m andn(m,n inclusively).
...
阅读全文
Description
We give the following inductive definition of a “regular brackets” sequence:
the empty sequence is a regular brackets sequence,
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
if a and b are regular brackets sequences, then ab is a regular brackets sequence.
no other sequence is a regular brackets sequence
For instance, all of the follo...
阅读全文
Problem Description
The professors of the Bayerische Mathematiker Verein have their annual party in the local Biergarten. They are sitting at a round table each with his own pint of beer. As a ceremony each professor raises his pint and toasts one of
the other guests in such a way that no arms cross.
Figure 2: Toasting across a table with eight persons:no arms crossing(left), arms crossing(r...
阅读全文
Description
The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on
the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the...
阅读全文
题意：给出一个01串的长度n,(1~10000000)，和m对二元组，每个二元组后面跟even或者odd，表示该二元组里面的1的个数为奇数或者偶数，问最早出现错误的二元组的下标，错误即为，满足前面条件的，但不满足当前的条件的。
很明显看出是并查集，而且n的范围远大于m，可以先离散化处理每个二元组的下标，然后在按照普通并查集那样处理就行了。我遇到一个坑自己的地方，即开始初始化father数组是用for（1～n）fa[i] = i;，但是很明显...
阅读全文
题意：给出n*m的只包含‘X’或‘O’的矩阵，可以将一个联通块内所有相连的X翻转成O，也可以将相连的O翻转成X，（相连指有一边相连）问翻转到同一种字符的最少次数
将联通块缩点，然后到别的联通块的距离就是翻转到该联通块需要的次数，对以每个联通块为起点跑一次最短路，求出最长距离，然后在最长距离里面找最短的就行了
/*************************************************************************
> File Name: a.cpp...
阅读全文