闲话
VP就写了ABC,DE后来写了一下发现不难.但是时间上太赶了.
A. Hotelier
题目大意:有个(n)个操作以及(10)个房间,操作有三种情况,一种是L,此时从最左边的空房间给人入驻,R则是找到最右边的空房间入住.如果是一个数字则表示让对应房间的人离开.问(n)个操作之后的房间状态.
数据范围:
(1 leq n leq 10^5)
房间标号仅有(0-9)
思路
显然每一次的过程就是找到最左端和最右端还能用的地方,直接用set的前后端并动态的增加删除即可.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;
char s[N];
int res[10];
int main()
{
int n;scanf("%d",&n);
scanf("%s",s + 1);
set<int> st;for(int i = 0;i <= 9;++i) st.insert(i);
for(int i = 1;i <= n;++i)
{
if(s[i] == 'L')
{
int t = *st.begin();st.erase(t);
res[t] = 1;
}
else if(s[i] == 'R')
{
int t = *(--st.end());st.erase(t);
res[t] = 1;
}
else
{
int c = s[i] - '0';
st.insert(c);
}
}
for(int i = 0;i <= 9;++i)
if(st.count(i)) printf("0");
else printf("1");
return 0;
}
B. Block Adventure
题目大意:有(n)个柱子,每柱子上有(h_i)个石头,初始在(1)位置,一步一步往后走,当前在(h_i)时可以把柱子上的石头放进自己的背包,如果(|h_{i+1} - h_i| leq k)则可以从(h_i)走到(h_{i+1}).背包最开始携带(m)个石头,问是否能移动到(n)号柱子上.
数据范围:
(1 leq n leq 100)
(0 leq m,k leq 10^6)
(0 leq h_i leq 10^6)
思路
由于过程是连续的一步一步走的,所以可以直接对每一步进行模拟.
-
若(h_i geq h_{i+1})时,则可以往背包里面增加(h_i - h_{i+1} + min(h_{i+1},k))个石头.这个式子的意思就是先把(h_i)拿到(h_{i+1}),再拿若干个石头让(h_i)变成(h_i - k)也就是极限能过去的高度.
-
若(h_i < h_{i+1})时,还需要继续划分讨论:
①若当前是满足条件的,也即(h_{i+1} - h_i leq k)那么类似上一种情况可以拿(max(0,k - h_{i+1} + h_i))石子走.
②如果当前不满足条件,则需要从背包里拿若干个石子把这个柱子堆够高度,需要(h_{i+1}-h_i-k)个足够就往下.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int h[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,m,k;scanf("%d%d%d",&n,&m,&k);
for(int i = 1;i <= n;++i) scanf("%d",&h[i]);
int ok = 1;
for(int i = 1;i <= n - 1;++i)
{
if(h[i] >= h[i + 1])
{
int take = h[i] - h[i + 1] + min(h[i + 1],k);
m += take;
h[i] -= take;
if(abs(h[i] - h[i + 1]) > k)
{
ok = 0;
break;
}
}
else
{
if(h[i + 1] - h[i] > k)
{
int need = h[i + 1] - h[i] - k;
if(m < need)
{
ok = 0;
break;
}
m -= need;
}
else
{
int take = min(h[i],k - h[i + 1] + h[i]);
take = max(take,0);
m += take;
h[i] -= take;
if(abs(h[i] - h[i + 1]) > k)
{
ok = 0;
break;
}
}
}
}
if(!ok) puts("NO");
else puts("YES");
}
return 0;
}
C. Round Corridor
题目大意:去原网站看图,难描述.
数据范围:
(1 leq n,m leq 10^{18})
思路
看到这个数据范围,肯定就只是(O(1))或者(O(logn))级别的.画几个图之后可以发现这个走廊的形态与(gcd(n,m))有关,整个图会被划分成(gcd(n,m))组,则对于内环来说,每(dfrac{n}{g})个是一组,外环每(dfrac{m}{g})个是一组.而且各自组的编号如果相同的话就意味着是联通的,直接进行判断就可以了.不过要注意下标的问题,比较好的做法是先把坐标减掉(1)再除循环节长度.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
if(y == 0) return x;
return gcd(y,x % y);
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
ll n,m,q;cin >> n >> m >> q;
ll g = gcd(n,m);
ll sec1 = n / g,sec2 = m / g;
while(q--)
{
ll sx,sy,ex,ey;cin >> sx >> sy >> ex >> ey;
ll f_from,s_from;
if(sx == 1) f_from = (sy - 1) / sec1 + 1;
else f_from = (sy - 1) / sec2 + 1;
if(ex == 1) s_from = (ey - 1) / sec1 + 1;
else s_from = (ey - 1) / sec2 + 1;
if(f_from == s_from) puts("YES");
else puts("NO");
}
return 0;
}
D. White Lines
题目大意:有一个像素画上有黑点和白点.有一个长度为(k)的正方形橡皮擦可以把整个区域里的黑色点变白色.问进行擦除一次之后,整个图上全是白色的行或者列的个数最多有多少个.
数据范围:
(1 leq k leq n leq 2000)
思路
一个比较容易想到的方向是这个题可能和前缀和有关.除此之外从复杂度上好像得不到什么信息.由于答案是统计行与列的个数的,所以可以单独考虑行与列的答案个数.
如果对于第(i)行来说,他可以被某次修改之后变成一个纯白的行,条件跟整行的第一个黑点和最后一个黑点有关,记作(L)和(R).那么如果整个的距离比(k)大这一行肯定就不能被修改成白行,直接跳过.如果这一行一个都没有,说明答案最后必然有他,直接累加.最后一种可能就是通过某些修改可以使得这一行变成白色的.考虑把橡皮擦的左上角放在那些位置可以使这一行变白,模拟一下之后可以得到区域是:([i-k+1,i],[r-k+1,l])一个左上角一个右下角围成的区域.那么怎么记录这个信息呢?可以把整个区域里所有的值都加(1),表明如果左上角在这个区域,那么答案就可以增加一.这一步可以通过二分差分来做.
对于列也是同理.在做完了所有行列之后,把差分还原回去,得到的一个矩阵(A[i][j])就表示通过一个(k)大小的橡皮擦,放在((i,j))这个位置上可以得到的白行/白列的个数.最后加上一开始就是的就可以了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
char g[N][N];
int n,k,res[N][N];
int main()
{
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;++i) scanf("%s",g[i] + 1);
int pre = 0;
for(int i = 1;i <= n;++i)
{
int l = -1,r;
for(int j = 1;j <= n;++j)
{
if(g[i][j] == 'B')
{
if(l == -1) l = r = j;
else r = j;
}
}
if(l == -1 || r - l + 1 > k)
{
if(l == -1) ++pre;
continue;
}
int a = max(i - k + 1,1),b = max(1,r - k + 1);
int c = i,d = l;
res[a][b] ++;
res[a][d + 1] --;
res[c + 1][b] --;
res[c + 1][d + 1] ++;
}
for(int i = 1;i <= n;++i)
{
int l = -1,r;
for(int j = 1;j <= n;++j)
{
if(g[j][i] == 'B')
{
if(l == -1) l = r = j;
else r = j;
}
}
if(l == -1 || r - l + 1 > k)
{
if(l == -1) ++pre;
continue;
}
int a = max(r - k + 1,1),b = max(1,i - k + 1);
int c = l,d = i;
res[a][b] ++;
res[a][d + 1] --;
res[c + 1][b] --;
res[c + 1][d + 1] ++;
}
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
res[i][j] += res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1];
int cres = 0;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
cres = max(cres,res[i][j]);
printf("%d",cres + pre);
return 0;
}
E. Compress Words
题目大意:把(n)个字符串依次拼接起来,如果后一个的前缀和前面得到的字符串的后缀有相同的地方则可以合并起来.问最终的字符串是什么.
数据范围:
(1 leq n leq 10^5)
长度总和不超过(10^6)
思路
前一个的后缀和后一个的前缀,这不就是(KMP)吗.直接把新读入的字符串(S)接到正在构造的答案(res)的前面,再做一个(KMP).得到后缀的匹配就可以知道具体有多少位是得新加入(res)的了.但是这里有两个点要注意:首先对于新加入的字符串来说,可能会有新的字符串很短,而原来的字符串很长的情况出现,但是只有第二个字符串的长度的答案串的后缀有意义,前面都根本不需要纳入考虑.因此要先求一个(l)表示两个串的长度的较小者,并把答案串的末尾(l)个元素抠出来.其次两个串拼接的时候,可能会导致(KMP)额外匹配上一些东西,需要加特殊字符屏蔽掉答案串的前缀部分.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+7;
namespace KMP
{
int succ[N],f[N];
void build(string s)
{
s = ' ' + s;
succ[1] = 0;int n = s.size();
for(int i = 2,j = 0;i <= n;++i)
{
while(j > 0 && s[i] != s[j + 1]) j = succ[j];
if(s[i] == s[j + 1]) ++j;
succ[i] = j;
}
}
void find(string a,string b)
{
build(a);int m = b.size(),n = a.size();
for(int i = 1,j = 0;i <= m;++i)
{
while(j > 0 && (j == n || b[i] != a[j + 1])) j = succ[j];
if(b[i] == a[j + 1]) ++ j;
f[i] = j;
//f[i] == n ?
}
}
};
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;cin >> n;
string res;cin >> res;
for(int i = 2;i <= n;++i)
{
string gt,s;cin >> s;
int l = min(s.size(),res.size());
int m = s.size();
gt = s + '#' + res.substr(res.size() - l,l);
KMP::build(gt);
for(int i = KMP::succ[gt.size()];i < m;++i) res += s[i];
}
cout << res << endl;
return 0;
}