第二天似乎考的不错嘿嘿嘿 但是数据水啊我也没有办法
Day2 知识点：：栈、队列（优先队列、单调队列）、堆、并查集
D2T1 OIER密码
问题描述
吉林省的OIER们保密意识很强，总是将信息加密。
有一个仅含小写字母的字符串，我们把它按如下方法加密：
步骤1：把所有连续的相同字母都用一个字母代替。比如 aaabbbb 被替换为 ab。
步骤2：在随机的位置插入两个相同的小写字母。重复 步骤2 很多次。
下面是一个加密的实例
初始字符串 jjjlloooiieerr 执行步骤1 之后变成 jloier
插入 aa 之后变成jloiaaer 插入 bb 之后变成jloiabbaer 插入 ll 之后变成jllloiabbaer
现在我们给定加密后的字符串，求执行 步骤1 之后的字符串是什么。
思路：
栈：步骤一的作用是保证原字符串中并没有两个或以上的连续字符，那我们可以存储字符串，一个字符一个字符的压栈，如果a[i]==a[i-1]的话，就将两个字符都弹出去 最后输出栈内字符即为答案
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[1000100];
char a[1000100];
int tmp;
int main()
{
scanf("%s",&s[0]);
int len=strlen(s);
for(int i=0;i<len;i++)
{
a[++tmp]=s[i];
if(tmp==1)continue;
if(a[tmp]==a[tmp-1])tmp-=2;
}
for(int i=1;i<=tmp;i++)
printf("%c",a[i]);
return 0;
}
D2T2 投资
问题描述
吉林省的OIER们投资了一支股票，大家都知道股票有赚有赔，现给出n天里这支股票的涨跌情况，都为整数，涨为正，跌为负。OIER们想知道天数在s到e之间的这只股票涨跌的最大连续和 。
思路：
f[i]是以第i个元素为结尾，并满足题意的最大连续和，那么：
f[i]=max(sum[i]-sum[j])(i-e<=j<=i-s) sum[i]代表a[1]~a[i]的和
所以用单调队列优化DP，使用前缀和
关于时间戳，看代码吧
最后，在求f[i]的时候记录一下最大值即为答案
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,x,y;
int q[110000];
int sum[110000];
int f[110000];
int l=1,r;
int ans=-10000000;
int main()
{
scanf("%d%d%d",&n,&x,&y);
for(int i=1;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
sum[i]=sum[i-1]+tmp;
}
for(int i=x;i<=n;i++)
{
while(l<=r&&sum[q[r]]>=sum[i-x])r--;
q[++r]=i-x;
while(l<=r&&q[l]<i-y)l++;
f[i]=sum[i]-sum[q[l]];
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}
D2T3 学习计划
问题描述
吉林省OIER们都是爱学习的同学，所以他们想学习更多的课程。长春市教育局开设了“云课程”网络学习平台，一共有n门课程，但这个平台有个弊端，就是每门课程在时间Ti之后将不再开放，并且每门课程要想学会需要Ci的时间，聪明的你帮助吉林省OIER们计划一下，使他们能够学习最多的课程。
思路：
std用的是优先队列，我写了一个并查集2333
貌似可以过？毕竟发现的问题是在分层（n<100）的暴力函数内挂的……
没错，你没看错，我暴力写挂了QAQ
但其实只是数据水啊 (其实极限数据能把我卡到0啊然而 90 嘿嘿嘿）
先贴一下我改过的代码：
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct your
{
int t,c;
}a[100100];
int n,temp,ans;
int f[100100];
int t[100100];
bool cmp(your j,your k)
{
if(j.c==k.c)return j.t>k.t;
return j.c<k.c;
}
int find(int x)
{
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
int check(int i)
{
for(int j=a[i].t;j>=1;)
{
if(t[j]!=0) t[j]=i,a[i].c--;
else
{
int tmp=find(j);
if(tmp==j)j--;
else j=tmp;
continue;
}
if(a[i].c==0)
{
ans++;
return 1;
}
j--;
}
return 0;
}
void work(int i)
{
if(check(i))
for(int j=a[i].t;j>=1;j--)
if(t[j]==i) t[j]=0,f[j]=find(j-1);
return ;
}
int main()
{
memset(t,-1,sizeof t);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].t,&a[i].c);
temp=max(temp,a[i].t);
}
sort(a+1,a+n+1,cmp);
f[0]=1;
for(int i=1;i<=temp;i++) f[i]=i;
for(int i=1;i<=n;i++) work(i);
printf("%d",ans);
return 0;
}这道题是贪心无疑 那么我们要怎么贪？
先按学习时间从小到大，若相等则按截止时间从大到小排序，那么我们设立一个t[];(time)
t[]分为3种情况：
t[]=-1 这个时间没有被占用 t[]=0这个时间已经确定被占用了 t[]!=0 && t[]!=1 这个时间还没有确定
以当前截止时间为终点 向前循环找 C[i]个空位，因为无法确定是否有C[i]个空位，标记t[j]=i;
如果能够找到C[i]个，那就再循环一遍将t[j]标记为0
这时候就会用到并查集了 面对t[]已经被标记为0，就可以维护并查集让find(t[])指向t[]前面第一个非0的t[]
然而面对极端数据会TLE (然而在师大OJ上也A了QAQ) 所以我们要考虑别的做法
首先按截止时间从小到大排序，定义一个已用时间变量，然后依次循环处理：如果当前工作耗时+已用时间小于截止时间，证明能干完，累加ans和已用时间并将耗时插入大根堆。否则判断堆顶元素，如果比当前工作耗时更大，则以当前工作耗时替换之，易得这样做合法且一定更优。
附上STD标程
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
priority_queue<int>q;
struct your
{
int t;
int c;
}a[100001];
bool cmp(your x,your y)
{
return x.t<y.t;
}
int n,ans;
int tmp;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].t,&a[i].c);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
if(a[i].c>a[i].t) continue;
if(tmp+a[i].c<=a[i].t)
{
ans++;
tmp+=a[i].c;
q.push(a[i].c);
}
else if(a[i].c<q.top())
{
tmp-=q.top();
tmp+=a[i].c;
q.pop();
q.push(a[i].c);
}
}
printf("%d",ans);
}至此 Day 2总结完毕23333
