今天上午考得不是很好，主要还是自己太弱QAQ
开场第一题给的图和题意不符，搞了半天才知道原来是走日字形的
然后BFS即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std; const int maxn=110;
int n,m,a,b,c,d;
int vis[maxn][maxn];
struct pos{
int x,y;
pos(int x=0,int y=0):x(x),y(y){}
};
queue<pos>Q;
int fx[8]={2,2,1,1,-1,-1,-2,-2};
int fy[8]={1,-1,2,-2,2,-2,1,-1}; int BFS(){
if(a==c&&b==d)return 0;
while(!Q.empty())Q.pop();
vis[a][b]=0;Q.push(pos(a,b));
while(!Q.empty()){
pos tmp=Q.front();Q.pop();
for(int i=0;i<8;++i){
int xx=fx[i]+tmp.x,yy=fy[i]+tmp.y;
if(xx<1||yy<1||xx>n||yy>m)continue;
if(vis[xx][yy]!=-1)continue;
if(xx==c&&yy==d)return vis[tmp.x][tmp.y]+1;
vis[xx][yy]=vis[tmp.x][tmp.y]+1;
Q.push(pos(xx,yy));
}
}return -1;
} int main(){
while(scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&d)==6){
memset(vis,-1,sizeof(vis));
int k=BFS();
if(k==-1)printf("impossible\n");
else printf("%d\n",k);
}return 0;
}
第二题给定一个无向图，询问有多少个环不属于任意一个简单环，有多少个环属于至少两个简单环
考试快结束才有点思路，然后码了一发边双一直在挂，最后也没有做出来
考试结束后听lyc说是点双，仔细分析了一下确实是，考试的时候太心急了
改成点双就A了
思路就很显然：点双中如果边数>点数，那么所有点至少属于两个简单环
如果边数<点数，那么不属于任意一个简单环
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int maxn=100010;
int n,m;
int h[maxn],cnt=0;
struct edge{
int to,next;
}G[maxn<<1];
int u,v;
int ans1,ans2;
int pre[maxn],low[maxn];
int vis[maxn],tim;
int dfs_clock,bcc_cnt;
vector<int>V;
stack<int>S; void add(int x,int y){
++cnt;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;
}
void Get_ans(){
int sz=V.size(),cnt=0;
for(int i=0;i<sz;++i){
int u=V[i];
for(int j=h[u];j;j=G[j].next){
int v=G[j].to;
if(vis[v]==tim)cnt++;
}
}
cnt>>=1;
if(cnt>sz)ans2+=cnt;
else if(cnt<sz)ans1+=cnt;
} void DFS(int u,int fa){
low[u]=pre[u]=++dfs_clock;
S.push(u);
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(!pre[v]){
DFS(v,u);low[u]=min(low[v],low[u]);
if(low[v]>=pre[u]){
V.clear();tim++;
for(;;){
int now=S.top();S.pop();
vis[now]=tim;V.push_back(now);
if(now==v)break;
}V.push_back(u);vis[u]=tim;
Get_ans();
}
}
else if(fa!=v)low[u]=min(low[u],pre[v]);
}return;
}
void Solve(){
ans1=ans2=0;
memset(pre,0,sizeof(pre));
memset(low,0,sizeof(low));
dfs_clock=bcc_cnt=0;
for(int i=1;i<=n;++i)if(!pre[i])DFS(i,-1);
printf("%d %d\n",ans1,ans2);
}
int main(){
while (scanf("%d%d",&n,&m)==2){
if(!n&&!m)break;
memset(h,0,sizeof(h));cnt=1;
for (int i=1;i<=m;++i){
scanf("%d%d",&u,&v);
u++;v++;
add(u,v);add(v,u);
}Solve();
}
return 0;
}
第三题给定一棵树，询问树上的路径中是否有长度等于k的
直接裸上树分治就可以啦，不到15min码完，1A
用哈希表可以做到O(nlogn)
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std; const int maxn=10010;
const int mod=521;
int n,u,v;
int h[maxn],cnt=0;
struct edge{
int to,next,w;
}G[maxn<<1];
int Q[maxn],k;
bool check[maxn],vis[maxn];
int f[maxn],w[maxn],sum,g;
int st[maxn],top;
int dis[maxn];
int a[maxn];
struct HASHMAP{
int h[mod+10],cnt;
int nxt[maxn<<1],st[maxn];
void init(){memset(h,0,sizeof(h));cnt=0;}
int ask(int k){
int key=k%mod;
for(int i=h[key];i;i=nxt[i]){
if(st[i]==k)return true;
}return false;
}
void push(int k){
int key=k%mod;
for(int i=h[key];i;i=nxt[i]){
if(st[i]==k)return;
}
++cnt;nxt[cnt]=h[key];h[key]=cnt;
st[cnt]=k;return;
}
}H;
void add(int x,int y,int z){
cnt++;G[cnt].to=y;G[cnt].next=h[x];G[cnt].w=z;h[x]=cnt;
}
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void cmax(int &a,int b){if(b>a)a=b;}
void Get_G(int u,int fa){
f[u]=0;w[u]=1;
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(vis[v]||v==fa)continue;
Get_G(v,u);w[u]+=w[v];
cmax(f[u],w[v]);
}cmax(f[u],sum-w[u]);
if(f[u]<f[g])g=u;
}
void Get_dis(int u,int f){
st[++top]=dis[u];
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(vis[v]||v==f)continue;
dis[v]=dis[u]+G[i].w;
Get_dis(v,u);
}return;
}
void Get_div(int u){
vis[u]=true;H.init();H.push(0);
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(vis[v])continue;
top=0;dis[v]=G[i].w;Get_dis(v,-1);
for(int j=1;j<=top;++j){
for(int now=1;now<=k;++now){
if(st[j]<=a[now])check[now]|=H.ask(a[now]-st[j]);
}
}
for(int j=1;j<=top;++j)H.push(st[j]);
}
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(vis[v])continue;
g=0;sum=w[v];Get_G(v,-1);
Get_div(g);
}return;
} int main(){
while(scanf("%d",&n)==1){
if(!n)break;
memset(h,0,sizeof(h));cnt=0;
for(int i=1;i<=n;++i){
while(scanf("%d",&u)==1){
if(!u)break;
scanf("%d",&v);
add(i,u,v);add(u,i,v);
}
}k=1;
while(scanf("%d",&a[k])==1){
if(!a[k])break;
k++;
}k--;
memset(vis,false,sizeof(vis));
memset(check,false,sizeof(check));
f[0]=0x7fffffff;sum=n;g=0;
Get_G(1,-1);Get_div(g);
for(int i=1;i<=k;++i){
if(check[i])printf("AYE\n");
else printf("NAY\n");
}printf(".\n");
}return 0;
}
第四题给定一个矩阵，询问最大子矩形
直接悬线法裸上就可以了，一开始为了秀技术写单调栈，一直WA
改成悬线法就过了，后来发现自己单调栈有个地方没有+1 QAQ
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std; const int maxn=1010; char s[maxn][maxn];
int map[maxn][maxn];
int n,m;
int T,ans,kase;
int h[maxn],l[maxn],r[maxn]; int Get_ans(int type){
int ans=0;
int L,R;
for(int j=1;j<=m;j++){h[j]=0;l[j]=1;r[j]=m;}
for(int i=1;i<=n;i++){
L=0;R=m+1;
for(int j=1;j<=m;j++){
if(map[i][j]==type){h[j]=0;l[j]=1;L=j;}
else{h[j]++;l[j]=max(l[j],L+1);}
}
for(int j=m;j>=1;j--){
if(map[i][j]==type){r[j]=m;R=j;}
else{r[j]=min(r[j],R-1);ans=max(ans,(h[j]+(r[j]-l[j]+1))*2);}
}
}return ans;
} int main(){
scanf("%d",&T);
while (T--){
ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='B')map[i][j]=0;
if(s[i][j]=='R')map[i][j]=1;
}
}
ans=max(ans,Get_ans(1));
ans=max(ans,Get_ans(0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if((i+j-1)&1)map[i][j]^=1;
}
}
ans=max(ans,Get_ans(1));
ans=max(ans,Get_ans(0));
printf("Case #%d: %d\n",++kase,ans);
}return 0;
}
第五题暂时还没有弄懂
第六题是UVa某题的变形，结果发现自己并不会变形之后的问题
首先很重要的一件事情是蚂蚁的相对位置不会改变
我们不妨把让转换参考系，让向左走的蚂蚁每次走2m/S，向右走的蚂蚁不动
这样很容易就可以计算出向左走的蚂蚁的贡献，向右走的蚂蚁由于颜色一直不动，贡献也是易于计算的
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std; typedef long long LL;
const int maxn=100010;
int n,k,d[maxn],b[maxn],sum[maxn],tmp[maxn];
int now;
bool vis[maxn];
LL ans[maxn];
char s[10]; int main(){
scanf("%d%d",&n,&k);
scanf("%d",&d[n+1]);
for(int i=1;i<=n;++i){
scanf("%d%d%s",&d[i],&b[i],s);
vis[i]=(s[0]=='L');
if(!vis[i])ans[b[i]]+=(d[n+1]-d[i])<<1;
}
for(int i=n;i>=0;--i){
for(int j=0;j<k;++j)ans[j]+=sum[j]*(d[i+1]-d[i]);
if(!vis[i]){
for(int j=0;j<k;++j)tmp[(j+b[i])%k]=sum[j];
for(int j=0;j<k;++j)sum[j]=tmp[j];
}else sum[b[i]]++;
}
for(int i=1;i<=n;++i){
if(vis[i])ans[(now+b[i])%k]+=d[i];
else now=(now+b[i])%k;
}
for(int i=0;i<k;++i){
printf("%lld.",ans[i]>>1);
if(ans[i]&1)printf("5\n");
else printf("0\n");
}return 0;
}
上午只做出了1、3、4,
其中第一题是BFS题目，第三题是树分治的模板题，第四题是悬线法的模板题
第二题太心急了，仔细想想如果发现是点双就可以A了
第五题和第六题是真没看出来
感觉上午发挥的很糟糕，主要是心态问题