[Usaco2006 Dec]Milk Patterns

Time Limit:5000MS  Memory Limit:65536K
Total Submit:9 Accepted:6
Case Time Limit:1000MS

Description

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天
产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。
John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的
牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。
比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。

Input

* Line 1: 两个整数 N,K。

* Lines 2..N+1: 每行一个整数表示当天的质量值。

Output

* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度

Sample Input

8 2
1
2
3
2
3
2
3
1

Sample Output

4

Source

Gold

直接上Hash。。二分判断就可以了。。代码0.7K囧。。
Code：

#include <algorithm>
#include <cstdio>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
const int seed=1333331,maxn=20000;
using namespace std;
typedef unsigned long long ull;
ull P[maxn];
int n,k,A[maxn];
bool Check(int L)
{
ull ret=0;map<ull,int> M;
rep(i,L) ret*=seed,ret+=A[i];
M[ret]=1;
rep(i,n-L)
{
ret-=P[L-1]*A[i];ret*=seed;ret+=A[i+L];
int&x=M[ret];if(++x>=k)return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&k);rep(i,n)scanf("%d",A+i);
P[0]=1;rep(i,n-1)P[i+1]=P[i]*seed;
int l=0,r=n/k+1;
while(l+1<r)
{
int m=(l+r)/2;
if(Check(m)) l=m;
else r=m;
}
printf("%dn",l);
}

在TopCoder上做题目。不会用Marco是不行的，神通广大的Marco能让你的AC时间减少一半甚至以上囧。。这次我潜心研究了TopCoder上各个神牛的Marco，做了个整理。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define SORT(x) sort(all(x))
#define CLEAR(x) memset(x,0,sizeof(x))
#define FILL(x,c) memset(x,c,sizeof(x))
#define MP make_pair
const int inf=~0U>>1;
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef set<int> si;
typedef si::iterator sit;
typedef map<int,int> mii;
typedef mii::iterator mit;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef istringstream ISS;
typedef ostringstream OSS;
template<class T> string tostr(T a)
{
OSS out;out<<a;return out.str();
}
int main()
{
int t=100;
long long T[2];
cout<<tostr(t)<<endl;
FILL(T,-1);
cout<<T[1]<<endl;
}

[Usaco2009 Feb]Revamping Trails

Time Limit:10000MS  Memory Limit:65536K
Total Submit:43 Accepted:13
Case Time Limit:1000MS

Description

每天,农夫John需要经过一些道路去检查牛棚N里面的牛. 农场上有M(1<=M<=50,000)条双向
泥土道路,编号为1..M. 道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N).
John需要T_i (1 <= T_i <= 1,000,000)时间单位用道路i从P1_i走到P2_i或者从P2_i
走到P１_i

他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新K (1 <= K <= 20)条路经，
将它们所须时间减为０．帮助FJ选择哪些路经需要更新使得从１到N的时间尽量少.

Input

* 第一行: 三个空格分开的数: N, M, 和 K

* 第2..M+1行: 第i+1行有三个空格分开的数：P1_i, P2_i, 和 T_i

Output

* 第一行: 更新最多Ｋ条路经后的最短路经长度．

Sample Input

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

Sample Output

1

Hint

K是1; 更新道路3->4使得从３到４的时间由１００减少到０. 最新最短路经是1->3->4,总用时
为１单位.
N<=10000

Source

Gold
这个很明显是分层图的最短路，不过我的做法有点诡异。就是对每一层用dijstra算出最短路之后再更新下一层。那样空间消耗很低而且速度比标程快一倍晕。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int maxn=10000+10;
typedef long long ll;
const ll inf=ll(1)<<60;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void InsEdge(int s,int t,int c){E[s].pb(Edge(t,c));E[t].pb(Edge(s,c));}
int n,m,k;
ll Dp[2][maxn];
struct State
{
int p;ll c;
State(int _p,ll _c):p(_p),c(_c){}
bool operator<(const State&o)const
{return c>o.c;}
};
priority_queue<State> Q;
int main()
{
cin>>n>>m>>k;int s,t,c;
rep(i,m)scanf("%d %d %d",&s,&t,&c),InsEdge(s-1,t-1,c);
int now=0,next=1;rep(i,n)Dp[next][i]=inf;Dp[next][0]=0;
rep(o,k+1)
{
swap(now,next);
rep(i,n)if(Dp[now][i]!=inf) Q.push(State(i,Dp[now][i]));
//Update now
while(Q.size())
{
State t=Q.top();Q.pop();if(Dp[now][t.p]!=t.c)continue;
Dp[now][t.p]=t.c;int ncost;
for(eit e=E[t.p].begin();e!=E[t.p].end();++e)
if((ncost=t.c+e->c)<Dp[now][e->t])
Dp[now][e->t]=ncost,Q.push(State(e->t,ncost));
}
//Update next
rep(i,n) Dp[next][i]=Dp[now][i];
rep(i,n) for(eit e=E[i].begin();e!=E[i].end();e++)
Dp[next][e->t]<?=Dp[now][i];
}
cout<<Dp[now][n-1]<<endl;
}

这道题是说给你一个最大8*8的矩阵，每次你可以交换两行或两列，让它的行优先遍历的字典序最小。。
实际上很简单，前天我钻研了楼教主的部分搜索的论文，这道题目实际上部分搜索就可以了，只要列的排列顺序确定了，行只要排个序就可以了。。
那么效率就是(n!*n^2*logn)对付这题n=8足够了。。
晕。。真的不能再搞编程了。。还有1个星期就要数学竞赛了天啊。。神啊。保佑我吧囧。。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
const int inf=~0U>>1;
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
class MatrixGame {
public:
vector <string> getMinimal(vector <string>);
};
int n,m;
vector<string> tmp,M,ans;
bool used[10]={0};
void dfs(int p)
{
if(p==m)
{
vector<string> t=tmp;
sort(all(t));
ans=min(ans,t);
return;
}
rep(i,m)if(!used[i])
{
used[i]=true;
rep(j,n) tmp[j][p]=M[j][i];
dfs(p+1);
used[i]=false;
}
}
vector <string> MatrixGame::getMinimal(vector <string> _M) {
ans=M=_M;
n=M.size();m=M[0].size();
tmp.resize(n);rep(i,n)tmp[i].resize(m);dfs(0);
return ans;
}

//Powered by [KawigiEdit] 2.0!

晕。。这道题目其实不算太难。当时脑子小了囧。。
只要dp就可以了。实际上由于黑色的最多只有8个，那么状态就是（usedRow，usedCol，LeftRow,LeftCol）.其中最后一个没必要储存，是有前三个唯一确定的。。
首先把黑色的全往左上角扔。。那么左上角的“黑块”最多只有8*8大小。
usedRow就是黑块的row的占用情况，usedCol就是黑块的Col占用的情况，LeftRow就剩下的没被占用的白色Row，LeftCol也一样，然后Dp就可以了囧。。最恶心的是如果边界情况就是没有任何后继的话答案应该是1，但不能根据答案是否为0判断，因为它也可能恰好是10000000007的倍数额啊囧。。好吧code太ugly了囧。。
手机买了居然是山寨的晕死。。现在高仿太多了囧。。
Code：
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
const int inf=~0U>>1;
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef long long ll;
typedef unsigned long long ull;

class DrawingBlackCrosses {
public:
int count(vector <string>);
};
const int maxn=20;
const ll mod=1000000007;
bool a[maxn][maxn];
int bn,bm,n,m;
ll Dp[maxn+1][1<<8][1<<8];
bool S[maxn+1][1<<8][1<<8]={0};
ll dfs(int ur,int uc,int ln,int lm)
{
ll&x=Dp[ln][ur][uc];
if(S[ln][ur][uc]) return x;
S[ln][ur][uc]=true;x=0;bool ok=false;
rep(i,bn)rep(j,bm)if((ur&(1<<i))==0&&(uc&(1<<j))==0&&!a[i][j])
x+=dfs(ur^(1<<i),uc^(1<<j),ln,lm),x%=mod,ok=true;
if(lm>0)rep(i,bn)if((ur&(1<<i))==0) x+=dfs(ur^(1<<i),uc,ln,lm-1)*lm,x%=mod,ok=true;
if(ln>0)rep(i,bm)if((uc&(1<<i))==0)x+=dfs(ur,uc^(1<<i),ln-1,lm)*ln,x%=mod,ok=true;
if(ln>0&&lm>0)x+=dfs(ur,uc,ln-1,lm-1)*ln*lm,x%=mod,ok=true;
if(!ok)x=1;
return x;
}
int DrawingBlackCrosses::count(vector <string> field) {
vector<string>T(all(field)),A;
sort(all(T));
reverse(all(T));
rep(i,T[0].size())
{
string a="";
rep(j,T.size())
{
a+=T[j][i];
}
A.pb(a);
}
sort(all(A));
reverse(all(A));bn=bm=0;n=A.size();m=A[0].size();
rep(i,n)rep(j,m)
{
a[i][j]=A[i][j]==’B’;
if(a[i][j]) bn>?=i+1,bm>?=j+1;
}
return dfs(0,0,n-bn,m-bm);
}

    晕。。这次的比赛真诡异。。250分说白了就是给你一个10位整数改变最少的数位把他变成因子数为奇数的数。。因子数为奇数那么所有素因子的幂数都是偶数，就是平方数额，暴力枚举平方数就行了囧。。这道题目在VIJOS上好像有类似的啊，就是那个什么关路灯的。。本质是差不多的囧。。
500分我沙茶的要死推不出公式直接Dp囧。。现在想出公式了囧。。真是太菜了。。
最后一题神牛题啊。。半点思路都没有晕。。先想是不是跟匹配有关系发现没关系，然后想容斥原理，还是没办法，然后想Dp，根本Dp不了。只好撞墙囧。。
Cha的时候我脑子小了。。一个也没cha成囧。。
最后第99名晕。。

[SCOI2003]字符串折叠

Time Limit:10000MS  Memory Limit:165536K
Total Submit:21 Accepted:15
Case Time Limit:1000MS

Description

折叠的定义如下：
1. 一个字符串可以看成它自身的折叠。记作S  S
2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)  SSSS…S(X个S)。
3. 如果A  A’, BB’，则AB  A’B’
例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B)  AAACBB，而2(3(A)C)2(B)AAACAAACBB
给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

Input

仅一行，即字符串S，长度保证不超过100。

Output

仅一行，即最短的折叠长度。

Sample Input

NEERCYESYESYESNEERCYESYESYES

Sample Output

14

Hint

一个最短的折叠为：2(NEERC3(YES))

Source
晕。。SCOI这种类型的题目怎么这么多囧。。这道题差不多吧，也是Dp，比压缩还简单，就不说了。。
另外<?=这个操作符很NB。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxl=120;
char M[maxl];
bool S[maxl][maxl]={0};
int Dp[maxl][maxl];
bool Match(int p,int Len,int s)
{
if(Len%s)return false;
rep(i,Len) if(M[p+i]!=M[p+i%s]) return false;
return true;
}
int Cost(int x)
{
if(x<10) return 1;
return 1+Cost(x/10);
}
int dfs(int l,int r)
{
int&x=Dp[l][r];if(S[l][r]) return x;
S[l][r]=true;int Len=r-l+1;x=Len;if(Len==1) return x;
for(int k=l;k<r;k++)x<?=dfs(l,k)+dfs(k+1,r);
for(int k=1;k<Len;k++)if(Match(l,Len,k))x<?=dfs(l,l+k-1)+2+Cost(Len/k);
return x;
}
int main()
{
//freopen("in","r",stdin);
cin>>M;
cout<<dfs(0,strlen(M)-1)<<endl;
}

[SCOI2007]压缩

Time Limit:1000MS  Memory Limit:165536K
Total Submit:18 Accepted:10

Description

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中 M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程：

另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

Input

输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。

Output

输出仅一行，即压缩后字符串的最短长度。

Sample Input

bcdcdcdcdxcdcdcdcd

Sample Output

12

Hint

在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。
【限制】
50%的数据满足：1<=n<=20
100%的数据满足：1<=n<=50
100%的数据满足：1<=n<=50

Source
其实是蛮简单的一道题啊，就是Dp啊，但是各种东西太纠结了。。我WA了N次。。。

晕死，状态定义就是（l,r,t）表示l到r的字串，t表示中间能否放M。。关键就是如果后面放了R的话中间就不能放M了晕死。。WA了这么多次，不想活了囧。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxl=100;
char M[maxl];
bool S[maxl][maxl][2]={0};
int Dp[maxl][maxl][2];
bool Match(int p,int Len,int s)
{
if(Len%s)return false;
rep(i,Len)if(M[p+i]!=M[p+i%s])return false;
return true;
}
inline int Update(int&x,int c){x=min(x,c);}
int dfs(int l,int r,bool t)
{
int&x=Dp[l][r][t];if(S[l][r][t]) return x;
S[l][r][t]=true;int Len=r-l+1;x=Len;
if(Len==1)return x;
if(t)for(int k=l;k<r;k++)Update(x,dfs(l,k,1)+1+dfs(k+1,r,1));
for(int k=l;k<r;k++)Update(x,dfs(l,k,t)+r-k);
if(Len%2==0&&Match(l,Len,Len/2)) Update(x,dfs(l,l+Len/2-1,0)+1);
return x;
}
int main()
{
//freopen("in","r",stdin);
cin>>M;
cout<<dfs(0,strlen(M)-1,1)<<endl;
}

[HAOI2008]圆上的整点

Time Limit:10000MS  Memory Limit:165536K
Total Submit:68 Accepted:22
Case Time Limit:1000MS

Description

求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。

Input

r

Output

整点个数

Sample Input

4

Sample Output

4

Hint

n<=2000 000 000

Source
额，我去查了查勾股数的生成方法，发现是这个样子的，
（n，m）=1,(n^2-m^2)^2+(2mn)^2=(n^2+m^2)^2。。同时三项全部乘个啥就可以推到所有数，所以首先枚举r/（n,m），再枚举n和m，再用个set去重就OK了。。
Code：

#include<iostream>
#include<set>
#include<utility>
using namespace std;
long long r,n,m;
typedef pair<int,int> ii;
set<ii> S;
int Cal(int d)
{
long long r=::r/d;
n=1,m=1;while(m*m<r)m++;
while(n<m)
{
while(n<m&&n*n+m*m>r)m–;
if(n>=m)break;
if(n*n+m*m==r){int a=m*m-n*n,b=2*m*n;S.insert(ii(a*d,b*d));S.insert(ii(b*d,a*d));}
n++;
}
}
int main()
{
cin>>r;int d;
for(d=1;d*d<r;d++)if(r%d==0) Cal(r/d)+Cal(d);
if(d*d==r)Cal(d);
cout<<S.size()*4+4<<endl;
}

[HAOI2008]玩具取名

Time Limit:10000MS  Memory Limit:165536K
Total Submit:45 Accepted:34
Case Time Limit:1000MS

Description

某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个 字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。

Input

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。
接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。
接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。
最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

Output

一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）
如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”

Sample Input

1 1 1 1
II
WW
WW
IG
IIII

Sample Output

IN

Hint

W可以变成II所以IIII可以缩成WW
IN均能变成WW所以WW又可以缩成I或者N
所以最终答案应该按照“WING”的顺序输出IN

[数据范围]
30%数据满足Len<=20，W、I、N、G<=6
100%数据满足Len<=200，W、I、N、G<=16

Source
水题啊。。直接Dp就可以了，Check（l，r，a）表示第l个到第r能否用第a个字母扩充出来
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxl=200+1;
int Map[256],D[4],L[4][16],R[4][16];
char Name[10]="WING";
char str[maxl];
bool S[maxl][maxl][4]={0};
bool Dp[maxl][maxl][4];
bool Check(int l,int r,int a)
{
bool&x=Dp[l][r][a];
if(S[l][r][a]) return x;
S[l][r][a]=true;
if(l==r) return x=(str[l]==Name[a]);
for(int k=l;k<r;k++)
rep(i,D[a]) if(Check(l,k,L[a][i])&&Check(k+1,r,R[a][i])) return x=true;
return x=false;
}
int main()
{
//freopen("in","r",stdin);
Map[‘W’]=0;Map[‘I’]=1;Map[‘N’]=2;Map[‘G’]=3;
rep(i,4)cin>>D[i];char l,r;
rep(i,4)rep(j,D[i]) cin>>l>>r,L[i][j]=Map[l],R[i][j]=Map[r];
cin>>str;int len=strlen(str);bool c=false;
rep(i,4)if(Check(0,len-1,i))cout<<Name[i],c=true;
if(!c)cout<<"The name is wrong!";
}