又是虚脱的一天啊QAQ,早上习惯性迟到，九点多到学校开始码题，六道题看下来花了将近一个小时，主要纠结于第二题和第六题。到了十点，没再深入思考，开始码题..
一直到十一点半，写了两道题。然后吃完饭后中午把剩下会的两道题水了水就开始去主攻第六题，第二题感觉不是很有思路。
然后就从三点想到四点，中间考量了很多算法好像都不行，但我能确定这是一道最短路的计数问题，相关的题目之前做过一道，但是面对这道题还不是很有想法。无奈，最后码了暴力走人。
今天没精力再改题了，一会还要补文化课的作业，具体的题解和小结什么的后天补上。
================================================
正经题解
改了一上午..终于改完了！
coins
这道题真的很水..但是整个机房只有神犇chadA掉了..其实就是正向边和反向边建个图，然后扫一遍就行了..
主要死于不能熟悉的运用DAG的性质，中间应该避免从一个点出发到另一个点存在多个路径导致方案数的重复计算。
//Graph T1 coins
//by Cydiater
//2016.10.2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "coins"
const int MAXN=2e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int LINK[MAXN],len=0,N,M,dfn[MAXN],low[MAXN],dfs_clock=0,group[MAXN],group_num=0,stack[MAXN],top=0,siz1[MAXN],siz0[MAXN],maxx=0,id=1;
bool vis[MAXN];
struct edge{
int y,next,v;
}e[MAXN];
namespace solution{
inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
void init(){
N=read();M=read();
up(i,1,M){
int x=read(),y=read();
if(x==y){
puts("IMPOSSIBLE");
exit(0);
}
insert(x,y,1);
insert(y,x,0);
}
}
void tarjan(int node){
dfn[node]=low[node]=++dfs_clock;
stack[++top]=node;vis[node]=1;
for(int i=LINK[node];i;i=e[i].next)if(e[i].v>0){
if(!dfn[e[i].y]){
tarjan(e[i].y);
low[node]=min(low[node],low[e[i].y]);
}else if(vis[e[i].y]) low[node]=min(low[node],dfn[e[i].y]);
}
if(dfn[node]==low[node]){
int tmp;group_num++;
do{
tmp=stack[top--];
vis[tmp]=0;
group[tmp]=group_num;
}while(tmp!=node);
}
}
bool pre_judge(){
memset(vis,0,sizeof(vis));
up(i,1,N)if(!dfn[i])tarjan(i);
memset(vis,0,sizeof(vis));
up(i,1,N) if(vis[group[i]]) return 0;
else vis[group[i]]=1;
return 1;
}
void dfs1(int node){
vis[node]=1;siz1[node]=1;
for(int i=LINK[node];i;i=e[i].next)if(e[i].v>0&&!vis[e[i].y]){
dfs1(e[i].y);
siz1[node]+=siz1[e[i].y];
}
}
void dfs0(int node){
vis[node]=1;siz0[node]=1;
for(int i=LINK[node];i;i=e[i].next)if(e[i].v<=0&&!vis[e[i].y]){
dfs0(e[i].y);
siz0[node]+=siz0[e[i].y];
}
}
int slove(){
if(!pre_judge())return -1;
up(i,1,N){
memset(vis,0,sizeof(vis));
dfs1(i);
memset(vis,0,sizeof(vis));
dfs0(i);
if(siz1[i]+siz0[i]-2>maxx){
maxx=siz1[i]+siz0[i]-2;
id=i;
}
}
return id;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
int ans=slove();
if(ans==-1)puts("IMPOSSIBLE");
else cout<<ans<<endl;
return 0;
}
maf
也是一道大水题..或者说是智商题，这道题是贪心，考场上想出了方案，但是没有想到可以用Topsort来维护相关性质，详细点讲吧。
1.被杀死的人最多即活着的人最少
活着的人最少，那么显然最后形成的图中满足任意两点之间不存在连边且点数最少。根据题目性质，每个点的出度都是1，所有这个图一定是由简单链，简单环，简单链套简单环组成的。
对于简单链，简单环，简单链套简单环，显然最少的可以活着的人都是1。所以只要统计出有多少个上述图就可以了。对于简单链和简单链套简单环，只需要统计出有多少个入度为0的点就行了。剩下的统计有多少个环也不必多说。
2.被杀死的人最少即活着的人最多
活着的人最多的情况相对来说是比较麻烦的。首先，让所有入度为0的点入队。然后这个点指向的点肯定die掉了，然后被杀的点所指向的点就少了一次被杀掉的机会。如果这时候这个点的入度恰好为0.那么这个也入队。重复几个。最后剩下的一定是环或者点，对于每个换，通过显然法可以证明每个环最多的能活下来的点为$\lfloor \frac{size}{2} \rfloor$，然后累加即可。
//NOIp Graph maf
//by Cydiater
//2016.10.4
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "maf"
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,kill[MAXN],indu[MAXN],q[MAXN<<2],head,tail,ans1,ans2;
bool die[MAXN],undie[MAXN];
namespace solution{
void init(){
N=read();
up(i,1,N)indu[kill[i]=read()]++;
}
void slove(){
memset(die,0,sizeof(die));
memset(undie,0,sizeof(undie));
head=1;tail=0;
up(i,1,N)if(indu[i]==0)q[++tail]=i;
ans1=tail;
for(;head<=tail;head++){
int node=q[head];ans2=tail;
if(die[kill[node]])continue;
die[kill[node]]=1;undie[kill[kill[node]]]=1;
if(--indu[kill[kill[node]]]==0)q[++tail]=kill[kill[node]];
}
up(i,1,N)if(indu[i]&&!die[i]){
int len=0,lea=0;
for(int j=i;!die[j];j=kill[j]){
die[j]=1;len++;
lea|=undie[j];
}
if(!lea&&len>1)ans1++;
ans2+=len/2;
}
cout<<N-ans2<<' '<<N-ans1<<endl;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
slove();
return 0;
}
board
大水题，不说
//Graph board
//by Cydiater
//2016.10.2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "board"
const int MAXN=1e6+5;;
const int oo=0x3f3f3f3f;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,-1,0,1};
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M,cnt=0,len=0,node[205][205],T,LINK[MAXN],dfn[MAXN],low[MAXN],stack[MAXN],top=0,group[MAXN],group_num,dfs_clock=0,head,tail,q[MAXN],dis[MAXN];
int ans=0;
char a[205][205];
struct edge{
int y,next,v;
}e[MAXN];
bool vis[MAXN],flag=0,cc[205][205];
namespace solution{
inline int get(int x,int y){
if(x>N||x<1||y>M||y<1) return T;
if(a[x][y]=='H') return T;
return node[x][y];
}
inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
void init(){
N=read();M=read();T=N*M+1;
up(i,1,N){
scanf("\n");
up(j,1,M){
scanf("%c",&a[i][j]);
}
}
up(i,1,N)up(j,1,M){
if(a[i][j]=='H')node[i][j]=T;
else node[i][j]=++cnt;
}
up(i,1,N)up(j,1,M)if(a[i][j]!='H'){
int num=a[i][j]-'0';
up(k,0,3){
int x=i+dx[k]*num,y=j+dy[k]*num;
insert(node[i][j],get(x,y),1);
}
}
}
void tarjan(int node){
dfn[node]=low[node]=++dfs_clock;
vis[node]=1;stack[++top]=node;
for(int i=LINK[node];i;i=e[i].next)
if(!dfn[e[i].y]){
tarjan(e[i].y);
low[node]=min(low[node],low[e[i].y]);
}else if(vis[e[i].y]) low[node]=min(low[node],dfn[e[i].y]);
if(dfn[node]==low[node]){
int tmp;group_num++;
do{
tmp=stack[top--];
vis[tmp]=0;
group[tmp]=group_num;
}while(tmp!=node);
}
}
void dfs(int x,int y){
if(flag)return;
if(x>N||x<1||y>M||y<1) return;
if(a[x][y]=='H') return;
if(a[x][y]=='0'){
flag=1;
return;
}
if(cc[x][y])return;
cc[x][y]=1;
up(i,0,3){
int tx=x+dx[i]*(a[x][y]-'0'),ty=y+dy[i]*(a[x][y]-'0');
dfs(tx,ty);
}
}
bool pre_judge(){
memset(cc,0,sizeof(cc));
dfs(1,1);
if(flag)return 0;
memset(vis,0,sizeof(vis));
up(i,1,T)if(!dfn[i])tarjan(i);
memset(vis,0,sizeof(vis));
up(i,1,T)if(vis[group[i]]) return 0;
else vis[group[i]]=1;
return 1;
}
void spfa(){
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
vis[node[1][1]]=1;dis[node[1][1]]=0;
head=1;tail=0;q[++tail]=node[1][1];
for(;head<=tail;head++){
int node=q[head];
for(int i=LINK[node];i;i=e[i].next)
if(dis[e[i].y]<dis[node]+e[i].v){
dis[e[i].y]=dis[node]+e[i].v;
if(!vis[e[i].y]){
vis[e[i].y]=1;
q[++tail]=e[i].y;
}
}
vis[node]=0;
}
}
int slove(){
if(!pre_judge())return -1;
spfa();
up(i,1,T)ans=max(ans,dis[i]);
return ans;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
cout<<slove()<<endl;
return 0;
}
kuglarz
你看，图论题，给你个矩阵，一般都是直接就把邻接矩阵给你了。然后考虑考虑这个题目的性质，显然是把横坐标+1跑最小生成树呀！
并查集写崩无限想扇自己
//Graph kug
//by Cydiater
//2016.10.2
#pragma GCC optimize("O2")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "kug"
const int MAXN=4e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,len,fa[MAXN];ll ans=0;
struct edge{
int x,y,v;
}e[MAXN];
namespace solution{
inline bool cmp(edge x,edge y){return x.v<y.v;}
int getf(int node){
if(fa[node]==node) return node;
fa[node]=getf(fa[node]);
return fa[node];
}
void init(){
N=read();
up(i,1,N)up(j,i,N){
int num=read();
e[++len]=(edge){i,j+1,num};
}
up(i,1,N+1)fa[i]=i;
}
void slove(){
sort(e+1,e+len+1,cmp);
up(i,1,len){
int x=e[i].x,y=e[i].y,v=e[i].v;
x=getf(x);y=getf(y);
if(x==y)continue;
ans+=1LL*v;fa[x]=y;
}
}
void output(){
cout<<ans<<endl;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
slove();
output();
//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
return 0;
}
blo
Tarjan 模板题，考察对Tarjan的理解。对于每条割点所连接的点。用乘法原理累加方案数就行了。
//Graph blo
//by Cydiater
//2016.10.2
#pragma GCC optimize("O2")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "blo"
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll N,M,LINK[MAXN],len=0,dfn[MAXN],low[MAXN],dfs_clock=0,siz[MAXN],ans[MAXN];
bool vis[MAXN];
struct edge{
int y,next,x;
}e[MAXN];
namespace solution{
inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].x=x;}
void init(){
N=read();M=read();
up(i,1,M){
int x=read(),y=read();
insert(x,y);
insert(y,x);
}
}
void tarjan(int node,int fa){
vis[node]=1;low[node]=dfn[node]=++dfs_clock;
ll tmp=0;siz[node]=1;
for(int i=LINK[node];i;i=e[i].next)
if(!dfn[e[i].y]){
tarjan(e[i].y,node);
low[node]=min(low[node],low[e[i].y]);
siz[node]+=siz[e[i].y];
if(low[e[i].y]>=dfn[node]){
ans[node]+=tmp*siz[e[i].y];
tmp+=siz[e[i].y];
}
}else if(vis[e[i].y]&&fa!=e[i].y) low[node]=min(low[node],dfn[e[i].y]);
ans[node]+=tmp*(N-tmp-1);ans[node]=(ans[node]+N-1)<<1;
}
void slove(){
memset(vis,0,sizeof(vis));
up(i,1,N)if(!dfn[i])tarjan(i,0);
}
void output(){
up(i,1,N)printf("%I64d\n",ans[i]);
}
}
int main(){
int __size__ = 20 << 20; // 20MB
char *__p__ = (char*)malloc(__size__) + __size__;
__asm__("movl %0, %%esp\n" :: "r"(__p__));
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
slove();
output();
return 0;
}
castle
考试的时候无限想和以前写过的一道题找关系，那道题是问每条边可以当多少次最短路。然后就GG了QAQ。
好吧其实这道题也不算难（至少比那道题要简单很多），先跑一遍SPFA，然后把dis排序，每个点扫一遍乘法原理xjb搞搞就行了。
//NOIp castle
//by Cydiater
//2016.10.4
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
#define FILE "castle"
const int MAXN=2e6+5;
const int oo=0x3f3f3f3f;
const ll mod=(1<<31)-1;
inline ll read(){
char ch=getchar();ll x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll N,M,LINK[MAXN],len=0,head,tail,ans=1,q[MAXN],eg[1005][1005];
struct edge{
ll y,next,v;
}e[MAXN];
bool vis[MAXN];
struct dist{
int id,v;
dist(){v=oo;}
}dis[MAXN];
namespace solution{
inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
inline bool cmp(dist x,dist y){return x.v<y.v;}
void init(){
N=read();M=read();
memset(eg,10,sizeof(eg));
up(i,1,M){
ll x=read(),y=read(),v=read();
insert(x,y,v);
insert(y,x,v);
eg[x][y]=min(eg[x][y],v);
eg[y][x]=eg[x][y];
}
}
void pret_SPFA(){
head=1;tail=0;
memset(vis,0,sizeof(vis));
up(i,1,N)dis[i].id=i;
vis[1]=1;dis[1].v=0;q[++tail]=1;
for(;head<=tail;head++){
int node=q[head];
for(int i=LINK[node];i;i=e[i].next)
if(dis[e[i].y].v>dis[node].v+e[i].v){
dis[e[i].y].v=dis[node].v+e[i].v;
if(!vis[e[i].y]){
vis[e[i].y]=1;
q[++tail]=e[i].y;
}
}
vis[node]=0;
}
}
void slove(){
pret_SPFA();
sort(dis+1,dis+N+1,cmp);
up(i,2,N){
ll tmp=0;
down(j,i-1,1){
int x=dis[i].id,y=dis[j].id;
if(dis[i].v==dis[j].v+eg[x][y])tmp++;
}
(ans*=tmp)%=mod;
}
}
void output(){
cout<<ans<<endl;
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
slove();
output();
//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
return 0;
}