CodeforcesRound#288(Div.2)题解

【A】水题&＃xff0c;模拟即可。

【B】水题&＃xff0c;模拟即可。

【C】

【题意】

有n个鬼魂拜访她
每个蜡烛可以产生t秒的光
每秒可以点一支蜡烛&＃xff0c;燃烧t秒
每个鬼魂拜访时至少有m个蜡烛
时间轴在[1,300] 【解题方法】

如果to11o11
第一个鬼魂出现的时间设为a[0]
a[0]-1,a[0]-2,a[0]-m都必须点蜡烛
然后呢&＃xff0c;第二个鬼魂呢&＃xff1f;看它这个点延续过来多少个蜡烛&＃xff0c;如果少&＃xff0c;就相应在提前位置点蜡烛 【复杂度分析】O(n^3)

【代码】

int a[333],b[333];
int main()
{int n,m,t;cin>>n>>t>>m;for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){int x;cin>>x;a[x] &＃61; 1;}if(t &＃61; i - need; st--){for(int j &＃61; st &＃43; 1; j <&＃61; st &＃43; t; j&＃43;&＃43;){if(j > 0) b[j]&＃43;&＃43;;}}}}}cout<}【D】给了n个3个字符的字符串&＃xff0c;这些字符串是一个字符串的字串&＃xff0c;问能不能找到一个长度为n&＃43;2的字符串使得满足这个条件&＃xff1f;

【解题方法】白书上例题&＃xff0c;把前两个字符和后两个字符hash成两个整数u,v&＃xff0c;然后u,v之间连接一条有向边。然后判断这个有相同是否有欧拉通路&＃xff0c;有的话&＃xff0c;画出来就可以了。

【代码】

【复杂度分析】O(n*logn)

【E】给了n个条件&＃xff0c;代表有n对()&＃xff0c;每个l,r代表第i对括号左右下标相差的范围&＃xff0c;问是否存在满足这个限制的括号序列&＃xff1f;
【解题方法】贪心&＃xff0c;可以用经典的栈来解决这个问题。步骤如下&＃xff1a;

1.当前字符串长&＃xff0b;1大于等于当前栈内元素个数&＃xff0b;当前区间左端点值&＃xff0c;相等时就是遇到一组匹配的"()"

2.若1且当前字符串长&＃xff0b;1小于等于当前栈内元素个数&＃xff0b;当前区间右端点值&＃xff0c;

3.若2则栈顶“(”出栈&＃xff0c;若不满足2则直接输出IMPOSSIBLE退出&＃xff0c;因为此时找不到与之匹配的")"&＃xff0c;相当于无解

条件2很好理解因为给了一个区间&＃xff0c;设"("的下标为l&＃xff0c;与之匹配的")"下标为r&＃xff0c;则有l &＃61; stack.size()&＃xff0c;r∈[l&＃43;l0&＃xff0c;l&＃43;r0]

最后若栈内还有元素则表示存在找不到匹配的"("&＃xff0c;则输出IMPOSSIBLE

【代码】

const int maxn &＃61; 2222;
int stk[maxn], top;
int pos[maxn], l[maxn], r[maxn];
char ans[maxn];
int len &＃61; 0;
int main()
{int n;cin>>n;bool ok &＃61; 1;for(int i &＃61; 0; i }