题目来自神犇chad
上次爆零是说着玩，这次真的爆零了QAQ
好吧貌似是TYVJ的模拟赛打多了..一直按照TYVJ的格式提交的压缩包..
然后莫名其妙就AK了hhh
来的时候迟到了半小时，昨晚痛苦的补作业补到了1点..，晚上补作业留下的泪就是白天浪时脑子里进的水
所以刚来的时候脑子有点昏，所以T1又是喜闻乐见的不会..
然后按照以往的套路滚去看T2
慢着...这道题好像有些眼熟？这不是我之前放在OJ上的一道题嘛 skip！
去看了看T3，Tarjan+分层图。可以，这很图论，水了一发模板
//chad round T3
//by Cydiater
//2016.9.16
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iostream>
#include <cstdlib>
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--)
typedef pair<int,int> pii;
#define FILE "trip"
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
,LEN=,Link[MAXN],group[MAXN],group_num=,dfn[MAXN],low[MAXN],dfs_clock=,stack[MAXN],top=,Node[MAXN][],cnt=,dis[MAXN],ans=;
priority_queue<pii, vector<pii>, greater<pii> >q;
bool vis[MAXN];
struct edge{
int x,y,next,v;
}e[MAXN],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;e[len].x=x;}
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;E[LEN].x=x;}
void init(){
N=read();M=read();K=read();
up(i,,M){
int x=read(),y=read(),v=read();
insert(x,y,v);
}
}
void tarjan(int node){
vis[node]=;dfn[node]=low[node]=++dfs_clock;
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]){
group_num++;
int tmp;
do{
tmp=stack[top--];
vis[tmp]=;
group[tmp]=group_num;
}while(tmp!=node);
}
}
void dijkstra(){
memset(dis,,sizeof(dis));
memset(vis,,sizeof(vis));
dis[Node[group[]][]]=;q.push(make_pair(dis[Node[group[]][]],Node[group[]][]));
while(!q.empty()){
pii tmp=q.top();q.pop();
int dist=tmp.first,node=tmp.second;
if(vis[node])continue;
vis[node]=;
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;
q.push(make_pair(dis[E[i].y],E[i].y));
}
}
}
void slove(){
memset(vis,,sizeof(vis));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
up(i,,N)if(!dfn[i])tarjan(i);
up(i,,N)up(k,,K)Node[i][k]=++cnt;
up(i,,len){
int x=e[i].x,y=e[i].y,v=e[i].v;
if(group[x]==group[y])continue;
up(k,,K) Insert(Node[group[x]][k],Node[group[y]][k],v);
up(k,,K-) Insert(Node[group[x]][k],Node[group[y]][k+],);
}
dijkstra();
}
void output(){
up(k,,K)ans=min(ans,dis[Node[group[N]][k]]);
)ans=-;
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
slove();
output();
;
}这些模板敲过好几遍了，不拍了。去看T1！
$ans \leq 50$
好呀，搞个二维前缀和枚举
//chad round T1
//by Cydiater
//2016.9.16
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <iomanip>
#include <ctime>
#include <cmath>
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 "papercut"
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
int N,M,K,cnt[MAXN][MAXN];
namespace solution{
void init(){
N=read();M=read();K=read();
memset(cnt,,sizeof(cnt));
up(i,,K){
int x=read(),y=read();
cnt[x][y]=;
}
up(i,,N)up(j,,M)cnt[i][j]=cnt[i-][j]+cnt[i][j-]-cnt[i-][j-]+cnt[i][j];
}
void slove(){
down(ans,min(min(N,M),),){
up(i,ans,N)up(j,ans,M){
int tmp1=cnt[i][j],tmp2=cnt[i][j-ans]+cnt[i-ans][j]-cnt[i-ans][j-ans];
){
printf("%d\n",ans);
return;
}
}
}
puts(");
}
}
int main(){
//freopen("input.in","r",stdin);
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
slove();
;
}然后水了水T2的模板
//chad round T2
//by Cydiater
//2016.9.16
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cmath>
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 "string"
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
char s[MAXN];
,ans=;
namespace solution{
inline bool equ(int x,int y,int l){return rank[x]==rank[y]&&rank[x+l]==rank[y+l];}
void init(){
scanf();
N=strlen(s+);
}
void suffix_sort(){
up(i,,N){rank[i]=s[i];sa[i]=i;}
,i,sig=,pos=;pos<N;sig=pos){
,i=N-l+;i<=N;i++)p[++pos]=i;
;i<=N;i++)if(sa[i]>l)p[++pos]=sa[i]-l;
;i<=sig;i++)cnt[i]=;
;i<=N;i++)cnt[rank[i]]++;
;i<=sig;i++)cnt[i]+=cnt[i-];
for(i=N;i;i--)sa[cnt[rank[p[i]]]--]=p[i];
,i=;i<=N;i++)tmp[sa[i]]=equ(sa[i],sa[i-],l)?pos:++pos;
;i<=N;i++)rank[i]=tmp[i];
l=l==?:l<<;
}
}
void get_height(){
,j=,k;i<=N;i++){
])){j=;continue;}
if(j)j--;
while(s[i+j]==s[k+j])j++;
height[rank[i]]=j;
}
}
void slove(){
suffix_sort();
get_height();
up(i,,N)ans+=N-sa[i]+-height[i];
}
void output(){
cout<<ans<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
using namespace solution;
init();
slove();
output();
;
}小结
除了T2出后缀数组比较坑，其他的题都很不错。其实NOIp通用的知识点就那么几个，关键还是看考试的状态。连着这几场考试都没有数论，很有可能是一个flag..
陷入LCT的坑无法自拔感觉各种基础算法都忘光了