大家……都能做出第三题来
T1: 给你n个和x、y轴平行的线段，问能够构成多少长方形n<=25,T<=100
这……就是四重循环让然后看一下就好
T2 : 给你一个吉他谱，然后让你找一个最方便的和弦转换方式使每个手指移动的距离和最小（题面竟然是错的！花了半天来理解样例才发现）
n<=5000 然后就是暴力dp写起来挺难受的
这两到2b题目就不放代码了
T3:给你一个图，每条边的权值是一个字符串，求字典序最小的路径N<=50,M<=500,len<=6
我写完第一道题（10min）的样子，然后看着道题目有人过了，于是就开坑了……然后被坑的好惨
一直在挂从未被超越
我的想法是对于每条边查成len+1个点和len条边这样每个边的边权都是1个字母然后我们枚举最大的字母寻找是否存在路径，如果存在路径那么输出，如果这里存在一个环，环上的点可以通过更大的字母联通到终点那么就是toughway。但是这样又有一个很难受的例子
4 4 0 3
0 1 aaa
1 2 aaa
0 2 aaaaa
2 3 b
然后这就是aaaaaab是答案，但是这样搞出来是aaaaab然后……算了，反正我这种蒟蒻
T4：
给你一个环，环上有n个n等分点，每个点有高度，选择两个点，高度之和加上两个点环上的最短距离最大，然后输出字典序最小的一对点。
环上问题改成链上复制一遍，每个点变成i的全职是高度加上等分距离*i。然后反正就是线段树查询区间最大值，然后注意字典序最小的时候要考虑环右边复制的字典序要比左边小。然后因为这个Wa了一发
//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <ctime>
#include <vector>
#include <deque>
#include <queue>
#include <string>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
int ret=0,f=1; char ch;
for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
if (ch=='-') f=-f;
for (;'0'<=ch && ch<='9';ch=getchar())
ret=ret*10+ch-'0';
return ret*f;
}
const int N = 200010;
struct node{
int l,r;
inline int mid(){ return r+l>>1; }
int mp;
}s[N<<2];
LL a[N],h[N],R;
int n;
inline int get(int x){
return x>n?x-n:x;
}
inline void push_up(int x){
int A=s[x<<1].mp,B=s[x<<1|1].mp;
s[x].mp=a[A]>a[B] || (a[A]==a[B] && get(A)<get(B))?A:B;
}
inline void build(int i,int l,int r){
s[i].l=l; s[i].r=r;
if (l==r){
s[i].mp=l;
return;
}
int m=l+r>>1;
build(i<<1,l,m);
build(i<<1|1,m+1,r);
push_up(i);
}
inline int query(int i,int l,int r){
if (s[i].l==l && s[i].r==r) return s[i].mp;
int m=s[i].mid();
if (r<=m) return query(i<<1,l,r);
else if (l>m) return query(i<<1|1,l,r);
else{
int A=query(i<<1,l,m),B=query(i<<1|1,m+1,r);
return a[A]>a[B] || (a[A]==a[B] && get(A)<get(B))?A:B;
}
}
inline void work(){
LL cur=0;
int al,ar;
for (int i=1;i<=n;i++){
int j=query(1,i+1,i+n/2);
LL tmp=a[j]-i*R+h[i];
int ll=i,rr=j;
if (rr>n) rr-=n,swap(ll,rr);
if (tmp>cur){
cur=tmp;
al=ll; ar=rr;
}else if (tmp==cur && (ll<al || (ll==al && rr<ar))){
al=ll; ar=rr;
}
}
printf("%d %d\n",al,ar);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int T=read();
for (int tt=1;tt<=T;tt++){
printf("Case #%d:\n",tt);
n=read(); R=read();
for (int i=1;i<=n;i++){
h[i]=read();
a[i]=R*(LL)i+h[i];
}
for (int i=n+1;i<=2*n;i++){
a[i]=i*R+h[i-n];
}
build(1,1,2*n);
work();
}
return 0;
}
T5:
意思是给你一个字符串，找到最短的不是这个字符串子序列的字符串，然后问有多少个
一开始看错题了，以为是cf461E后来发现不对这里的子序列不是连续的（不是子串）选取规则也不一样
然后就非常水了
Dp[i]表示一个二元组表示我们现在匹配到了第i个位置，最少使用多少个字符，有多少种方案
然后转移是一个区间[pre[i],i-1]（这里的pre[i]表示i前面和相同的字母出现的最后位置），可以用线段树优化(有一道线段树题目)
//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <ctime>
#include <vector>
#include <deque>
#include <queue>
#include <string>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
int ret=0,f=1; char ch;
for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
if (ch=='-') f=-f;
for (;'0'<=ch && ch<='9';ch=getchar())
ret=ret*10+ch-'0';
return ret*f;
}
const int N = 100010,mod=1000000007;
struct Ans{
int len,way;
Ans(int x=0,int y=0): len(x),way(y){}
}now;
inline Ans min(const Ans &a,const Ans &b){
if (a.len<b.len) return a;
else if (a.len>b.len) return b;
else return Ans(a.len,(a.way+b.way)%mod);
}
struct node{
int l,r;
inline int mid(){ return r+l>>1; }
Ans A;
}s[N<<2];
inline void push_up(int x){
s[x].A=min(s[x<<1].A,s[x<<1|1].A);
}
inline void build(int i,int l,int r){
s[i].l=l; s[i].r=r;
if (l==r){
return;
}
s[i].A=Ans(N,0);
int m=l+r>>1;
build(i<<1,l,m); build(i<<1|1,m+1,r);
}
inline Ans query(int i,int l,int r){
if (l>r) return Ans(N,0);
if (s[i].l==l && s[i].r==r) return s[i].A;
int m=s[i].mid();
if (r<=m) return query(i<<1,l,r);
else if (l>m) return query(i<<1|1,l,r);
else return min(query(i<<1,l,m),query(i<<1|1,m+1,r));
}
inline void modify(int i,int p){
if (s[i].l==s[i].r){
s[i].A=now;
return;
}
if (p<=s[i].mid()) modify(i<<1,p);
else modify(i<<1|1,p);
push_up(i);
}
int last[26],a[N],pre[N];
char st[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int T=read();
for (int tt=1;tt<=T;tt++){
printf("Case #%d:\n",tt);
scanf("%s",st+2);
st[1]='.';
int n=strlen(st+1);
build(1,1,n);
now=Ans(0,1);
modify(1,1);
for (int i=0;i<26;i++) last[i]=1;
for (int i=2;i<=n;i++){
a[i]=st[i]-'a';
pre[i]=last[a[i]];
last[a[i]]=i;
}
for (int i=2;i<=n;i++){
now=query(1,pre[i],i-1);
now.len++;
modify(1,i);
}
Ans ans=Ans(N,0);
for (int i=0;i<26;i++){
ans=min(ans,query(1,last[i],n));
}
printf("%d %d\n",ans.len+1,ans.way);
}
return 0;
}
T6看了以下完全不会
给你一个n个点m条边的有向图让你删去最多k条边，使得每个点的入读和初度的绝对值的最大值最小
n<=50 k<=m<=n*(n-1)
不会！
似乎有一点网络流的感觉但是这么少的人做出来应该不会是网络流吧。。。
评论 (0)
