A
模拟题
思路
先找到*，再找出边界，最后输出。然后找边界的最小值应该赋一个极大值
Code
char ch[101][101],c;
int p,q,x,y;
signed main(){
int n=read(),m=read();
p=x=0x3f;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>c;
ch[i][j]=c;
if(c=='*'){
if(i<=p) p=i;
if(j<=x) x=j;
if(i>=q) q=i;
if(j>=y) y=j;
}
}
for(int i=p;i<=q;i++){
for(int j=x;j<=y;j++)
printf("%c",ch[i][j]);
puts("");
}
return 0;
}
B
思路
暴力枚举即可
Code
int a[5005],ans=inf;
signed main(){
int n=read(),x0=read();
for(int i=0;i<n;i++){
int x=read(),y=read();
if(x>y) swap(x,y);//ai可能大于bi
for(int j=x;j<=y;j++){
a[j]++;//枚举点
if(a[j]==n)
if(abs(j-x0)<ans) ans=abs(j-x0);//找最大距离
}
}
if(ans==inf) ans=-1;
printf("%d
",ans);
return 0;
}
C
思路
对于每个点 看是否只有一个点和它是相同的
如果是 看输入的 4 条边是否 是 其中两条和 (x) 轴平行 另两条和 (y) 轴平行
Code
struct Node{
int x,y;
}p[10];
signed main(){
for(int i=0;i<8;i++) scanf("%d%d",&p[i].x,&p[i].y);
bool flag=true;
for(int i=0;i<8;i++){
int cnt=0;
for(int j=0;j<8;j++ )
if(p[i].x==p[j].x&&p[i].y==p[j].y) cnt++;
if(cnt!=2){flag=false;break;}
}
if(flag==false) return puts("NO"),0;
int tx=0,ty=0;
for(int i=0;i<4;i++){
if(p[i*2].x==p[i*2+1].x&&p[i*2].y!=p[i*2+1].y) tx++;
if(p[i*2].x!=p[i*2+1].x&&p[i*2].y==p[i*2+1].y) ty++;
}
if(!(tx==2&&ty==2)) flag=false;
if(flag) printf("YES");
else printf("NO");
return 0;
}
D
求树的直径，这里用的邻接矩阵,(dfs)求
思路
(n)个点，(n-1)条无向边求这个图中最长的两条不相交的链长度，
因为这里只有(n-1)条边，所以这一定不会存在环，
所以我们可以枚举每一条边，用这条边把图分成两部分，
求各自部分的树的直径，然后乘积，
(dfs)的时候记录最长和次长的树链长度
int dep,n,ch[maxn][maxn];//邻接矩阵
inline int dfs(int x,int y){
int maxx=0,maxx1=0,maxpath=0;
for(int i=1;i<=n;i++){
if(ch[i][x]&&i!=y){
int z=dfs(i,x);
if(maxpath<z) maxpath=z;
if(maxx<dep){
maxx1=maxx;
maxx=dep;
}
else if(maxx1<dep) maxx1=dep;
}
}
if(maxpath<maxx+maxx1) maxpath=maxx1+maxx;
dep=maxx+1;
return maxpath;
}
signed main(){
n=read();
for(int i=1;i<n;i++){
int x=read(),y=read();
ch[x][y]=ch[y][x]=1;
}
int ans=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(ch[i][j]){
int a=dfs(i,j);
int b=dfs(j,i);
ans=max(ans,a*b);
}
printf("%d",ans);
return 0;
}
E
(DP)
但可以优化到三维
题意：
给你一个数(N)，从(1)到(N)形成(t)个波峰和(t-1)个波谷,总共有多少种情况。
思路：
将问题分解为求(2 imes t-1)个转折点，设(dp[x][y][t])为当最后一点落在((x,y))上时，出现(t)个转折点的总数。那么对于当前点有两种情况，他的前一个点到当前点要么高度比他大，要么比他小。
若当前点((x,y))之前出现了(t)个转折点，若(t)为偶数，也就是说只要前一个点落点在当前点的下方，当前状态要想保持任然只出现偶数(t)个转折点的情况，则
[dp[x][y][t]=sum (dp[x-1][h][t])(1le h<y)
]
同时只要前一个点落在当前点的上方，都可以达到
[dp[x][y][t+1]=sum (dp[x][h][t])(y<hle 4)
]
当(t)为奇数时,同样的，
[dp[x][y][t]=sum (dp[x-1][h][t])(y<hle 4);
]
[dp[x][y][t+1]=sum (dp[x-1][h][t])(1le h<y)
]
当然，对于最开始的转折点一定是上升的。
Code
int dp[25][5][25];
signed main(){
for(int i=1;i<=3;i++) dp[1][i][0]=1;
for(int x=2;x<22;x++)
for(int y=1;y<=4;y++)
for(int t=0;t<21;t++)
for(int h=1;h<=4;h++){
if(x==2){
if(y>h){
if(t%2) dp[2][y][t+1]+=dp[1][h][t];
else dp[2][y][t]+=dp[1][h][t];
}
}
else{
if(t%2){
if(h>y) dp[x][y][t]+=dp[x-1][h][t];
else if(h<y) dp[x][y][t+1]+=dp[x-1][h][t];
}
else{
if(h<y) dp[x][y][t]+=dp[x-1][h][t];
else if(h>y) dp[x][y][t+1]+=dp[x-1][h][t];
}
}
}
int n=read(),t=read();
if(t*2+1>n||n>6*t+1) return puts("0"),0;
int ans=0;
for(int i=1;i<=4;i++)
ans+=dp[n][i][2*t-1];
printf("%d",ans);
return 0;
}