Time Limit: 10000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 820 Accepted Submission(s):
202
Problem Description
Given a positive integer n, your task is to find a positive integer m, which is a multiple of n, and that m contains the least number of different digits when represented in decimal. For example, number 1334 contains three different...
阅读全文
用的是EdmondsKarp
程序可以再优化的，懒得优化了
EdmondsKarp
#include <iostream>
#include<stdio.h>
#include <queue>
#include <limits>
#include <cstring>
using namespace std;
const int maxNode = 202;
int N = 201;//edge
int M = 201;//node
const int maxInt = numeric_limits<int>::max();
int g[maxNode][maxNode];
int f[maxNode][maxNode];
int residual[maxNode][max...
阅读全文
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1000;
int uN, vN; // u, v数目，要初始化！！！
bool g[MAXN][MAXN]; // g[i][j] 表示xi与yj相连
int xM[MAXN], yM[MAXN]; // xM[i]:cow i已经被分配到stall xM[i]; stall j 已经被分配给cow yM[j]
bool chk[MAXN]; // 辅助量检查某轮y[v]是否被check
bool SearchPath(int u){
int v;
for(v = 0...
阅读全文
题意：某个冰块上有a只企鹅，总共可以跳出去b只，问是否可能所有的企鹅都跳到某一块冰块上，输出所有的可能的冰块的编号。
由于每个点只能跳出去m只企鹅，所以要拆点假如不拆点，一个点到另一个点可能会跳多于m只企鹅通过拆点后u->u'间的容量来完成题目的要求（对点的一些限制）
建图：i->i+n 容量为m i+n->j容量为INF新建源点s，s->i的容量为i点企鹅的个数然后枚举汇点求最大流就可以判断某个点是否符合条件
Sour...
阅读全文
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
int n;
int a[66];
int v[66];
int dfs(int s,int s1,int minn)
{
int i;
if(s==0)
return 1;
if(s1 > s)
return 0;
if(s1==0)
s1=minn;
for(i=0;i<n;i++)
{
if(i&&(a[i]==a[i-1])&&(v[i-1]==0))
continue;
if((v[i]) || (s1 < ...
阅读全文
题目链接：http://poj.org/problem?id=2782
题目大意： 给出n袋长度不一定相同的垃圾，把它们全部装在长度不超过L的垃圾桶里；
每个垃圾桶至多有两袋垃圾，并且垃圾的长度相加小于L；
求最少用多少个垃圾桶可以装入全部垃圾；
解题思路： 每个垃圾桶最多只能有两袋垃圾，也就是说可以装是一袋或者两袋；
先排序，然后分别从最小、最大两个极端开始枚举：
...
阅读全文
题目链接：http://poj.org/problem?id=2785
题目大意： 给出四个长度为n的列表(从上到下)
从每个列表分别取出一个数据，使得相加的结果为0
问最多存在多少种情况?
解题思路： n的范围(1<=n<=4000)，如果直接搜索 O(n^4) 那么肯定TLE.(计算机每秒钟的运行速度大概是10^8)
可以转化为O(2*n^2)：
把1组和2组列表分别相加存到a[ ]数组中...
阅读全文
题目链接: http://poj.org/problem?id=3233
题目大意: 给出矩阵n*n的矩阵A，求对m取模后的结果
解题思路: k的非常大，直接求解时间复杂度太高
定义F[k]=A+A^2+A^3+....A^k
利用乘法的分配律可以减少运算 F[6]=A+A^2+A^3+A^4+A^5+A^6=(A+A^2+A^3)+(A+A^2+A^3)*A^3
每次运算二分减少规...
阅读全文
题目链接: http://poj.org/problem?id=3070
题目大意: 求Fibonacci数列第n项(0 ≤ n ≤
1,000,000,000)，对m取模后的结果
解题思路: 直接求解第n项，由于n太大，时间复杂度非常高
我们需要构造一个矩阵使得与(a,b)相乘后等于(b,a+b)
不防假设2x2矩阵为:
x1 x2 a b
X ...
阅读全文