机房测试8.16

2024-01-07 07:40

文章标签 测试 8.16 机房

本文主要是介绍机房测试8.16，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

完美子串

题目 & 数据范围

yyc非常喜欢完美的字符串，当然一个完美的字符串定是简约并且多样，当然一个完美的字符串定是简约并且多样的。现在 yyc 有一个字符串，他想知道这个字符串的完美子最小长度是多少。一个完美子串，是原的连续序列并且包含了不同的 26 个大写字母。

当然了如果 yyc的字符串中并不的字符串中并不存在完美子串，则输出 QwQ 。

20%: len<=1,000,数据随机。
40%: len<=2,000,
50%: len<=5,000,
70%: len<=300,000,
100%: len<=2,000,000,保证全为大写字母。

解题法

半小时秒杀！

~~（虽然别人dalao10min切掉）~~

一眼看出必须在O(n)范围内解决这个问题。

考虑扫到的某一个元素，如果不在最优答案中，一定因为后面出现了相同的字母。

与后面那个玩意相比，先进的必定先出，这就是队列。（FIFO）

对于一个串，每次读一位就Push进去，队列Size超过26之后，每一次O(26)check

对于队首，用桶装字母的出现次数，超过2就Pop。（一直Pop，一直Pop）

每一次合法子串就min一波，ans初值为子串长度。

代码

感觉这几天写的最舒服的程序了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define FN "str"
const int maxn=2e6+5;char c[maxn];
int tong[30],len;
int temp[30];std::queue<int> Q;int main() {freopen(FN".in","r",stdin);freopen(FN".out","w",stdout);char ch;while(ch<'A' || ch>'Z') ch=getchar();while(ch>='A' && ch<='Z') {c[++len]=ch;tong[ch-'A'+1]++;ch=getchar();}bool flag=true;for(int i=1;i<=26;i++)if(!tong[i]) {flag=false;break;}if(!flag) {printf("QwQ");return 0;}int ans=len,tl=0;for(int i=1;i<=len;i++) {Q.push(c[i]-'A'+1);tl++;temp[c[i]-'A'+1]++;while(temp[Q.front()]>1) {tl--;temp[Q.front()]--;Q.pop();}bool check=false;if(tl<26) check=true;else {for(int i=1;i<=26;i++)if(!temp[i]) {check=true;break;}}if(!check)ans=std::min(ans,tl);}printf("%d",ans);return 0;
}

游戏

问题描述 & 数据范围

everlasting觉得太无聊了，于是决定和蒟蒻 yyc 玩游戏！
他们会玩T轮游戏，每轮中有若干局，他们的初始积分为 1，每局的分值为k，输的人得分乘k ，输的人得分乘k^2。每轮游戏后， everlasting都会询问这次游戏双方的得分,但 yyc 记不住得分只能随口说两个。但他不知道这数最终会不成为两个人的得分。于是 yyc 决定向你求助！

T:1e6
x,y:1e9

解题法

将两个数相乘，看一看是不是一个数的立方，然后两个数除掉这个数，就是两个人分别赢的k的乘积，计算一下是否xxy==a和yyx==b就行了。

代码

std::code();

#include<bits/stdc++.h>
#define eps 1e-9
#define PI 3.141592653589793
#define bs 1000000007
#define bsize 256
#define MEM(a) memset(a,0,sizeof(a))
typedef long long ll;
using namespace std;
int ask(long long x)
{long long le=1,ri=1e6;long long mid;while(le<ri){mid=(le+ri)>>1;long long now=mid*mid*mid;if(now==x)return mid;else if(le*le*le==x)return le;else if(ri*ri*ri==x)return ri;else if(now<x)le=mid+1;elseri=mid;}return 0;}
int main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);int n;long long a,b;cin>>n;while(n--){scanf("%I64d %I64d",&a,&b);long long now=ask(a*b);if(now){if(a%now==0&&b%now==0)printf("Yes\n");elseprintf("No\n");}elseprintf("No\n");} return 0;}

泥泞的牧场

题目 & 数据范围

解题法

不能盖住好地，那么宽为1的木板只能放在行、列连通块里。
所以行、列连通块对应左、右部中的点，泥地对应边。
求二分图最小覆盖就是答案。
二分图最小点覆盖==最大匹配

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
//by zrt
//problem:
using namespace std;
typedef long long ll;
const double eps(1e-10);
int R,C,n;
char s[60][60];
int link1[1005];
int cover[1005];
int H[1005],X[1000050],P[1000050],tot;
inline void add(int x,int y){P[++tot]=y;X[tot]=H[x];H[x]=tot;
}
bool find(int x){for(int i=H[x];i;i=X[i]){if(cover[P[i]]) continue;cover[P[i]]=1;int q=link1[P[i]];link1[P[i]]=x;if(q==-1||find(q)) return 1;link1[P[i]]=q;}return 0;
}
int xx,yy;
int a[60][60],b[60][60];
int main(){freopen("cover.in","r",stdin);freopen("cover.out","w",stdout);memset(link1,-1,sizeof link1);scanf("%d%d",&R,&C);for(int i=0;i<R;i++){scanf("%s",s[i]);}for(int i=0;i<R;i++){for(int j=0;j<C;j++){if(s[i][j]=='*'){if(j>0&&s[i][j-1]=='*'){a[i][j]=a[i][j-1];}else a[i][j]=++yy;if(i>0&&s[i-1][j]=='*'){b[i][j]=b[i-1][j];}else b[i][j]=++xx;}}}for(int i=0;i<R;i++){for(int j=0;j<C;j++){if(s[i][j]=='*'){add(a[i][j],b[i][j]);}}}n=yy;int ans(0);for(int i=1;i<=n;i++){memset(cover,0,sizeof cover);if(find(i)) ans++;}printf("%d\n",ans);return 0;
}