UVA - 11536 Smallest Sub-Array(尺取法)
2024-08-23 11:24:07
题目:
思路:
读完题之后第一时间想到的是尺取法来做这个题,结果让自己写写崩了,还是练得少!!
到网上搜了一下学习了大佬的标记方法,用一个变量来判断是不是都已经出现,要比每次都判断一下快超多。
代码:
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1e3
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = ;
int a[maxn],vis[maxn];
int n,m,k; void init(){
memset(vis,,sizeof(vis));
a[] = ,a[] = ,a[] = ;
for(int i=; i<=n; i++){
a[i] = (a[i-]+a[i-]+a[i-])%m+;
}
} int main(){
// FRE();
int kase=,T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
init();
if(k > m || k>n){
printf("Case %d: sequence nai\n",++kase);
continue;
}
int ans = ;
int st=,en=,tot=;
while(en <= n){
int t = a[en++];
vis[t]++;
if(t<=k && vis[t]==) tot++;//标记区间个数get!! while(st<en && tot==k){
ans = min(ans, en-st);
t = a[st++];
vis[t]--;
if(t<=k && vis[t]==) tot--;//标记区间个数
}
//cout<<"en: "<<en<<" st: "<<st<<endl;
}
if(ans>n){
printf("Case %d: sequence nai\n",++kase);
}else{
printf("Case %d: %d\n",++kase,ans);
}
}
return ;
}
最新文章
- commonJS
- 设计模式之美:State(状态)
- 使用uiautomator做UI测试
- 【转】NPOI 单元格级别应用
- springmvc+mybatis+spring 整合 bootstrap
- [Effective JavaScript 笔记]第38条:在子类的构造函数中调用父类的构造函数
- win7 IIS发布项目遇到的问题
- 解决RPM包相互依赖的有效方法
- UI6_UIAlertContrller
- linux系统垃圾清理
- hive UDAF源代码分析
- jdk并发包 CopyOnWriteArrayList源代码分析
- Asp.Net MVC5入门学习系列③
- Java课程设计-随机密码生成器
- Nginx-动态路由升级版
- python全栈开发day110-Flask基础语法
- 服务程序在c#中的写法
- leetcode26: 删除排序数组中的重复项
- python 装饰器前之闭包和装饰器
- [poj 1947] Rebuilding Roads 树形DP