机房测试8.16

╰+哭是因爲堅強的太久メ 2021-10-23 06:47 236阅读 0赞

# 完美子串 #

## 题目 & 数据范围 ##

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的乘积，计算一下是否x*x*y==a和y*y*x==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; else ri=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"); else printf("No\n"); } else printf("No\n"); } return 0; }

# 泥泞的牧场 #

## 题目 & 数据范围 ##

![1447768-20180816151130474-1025889556.png][]

## 解题法 ##

不能盖住好地，那么宽为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; }

# 总结 #

T1秒杀之后完全梦游

好多AK啊！

难受的。

我在此立下FLAG：

辣个只有NOIP胸牌水平的辣鸡考200+绝对有猫腻 ！

MMP，明天看它吔屎。

不是很重要

今天莫名其妙时间去哪儿了?

无Fuck♂说。

转载于:https://www.cnblogs.com/LoLiK/p/9487529.html

[1447768-20180816151130474-1025889556.png]: /images/20211023/8221e68d88f9459ca85b4aaa477e5314.png