200天1000题 （DAY 8）
目前总题数： 36
目前CF分数： 1336（ +11 ）
今天打了一下 CF Round #822 （DIV2）
手速比以前快，过了3个题，D想到一个双指针贪心的写法，但实现出来的代码有漏洞，疯狂WA on Test 3
B题是最傻逼的，我把 i 写成 n 并且过于自信的交题，直接wa两发
C题也有一个傻逼的 wa， 我把 越界条件判断写后面了 导致 RE ON 4： While(某条件 && 越界判断) 改为 WHILE(越界判断&&某条件) 就过了
下面是A，B，C三题的题解。
T1. (Codeforces #822 Div2) A. Select Three Sticks
/*
题目大意：
给你n个数，a1，a2 …… an
你每次能选中其中一个数字使他减1
问，你最少做多少次操作才能够在 a1 ，a2 ，…… an中找到三个数组成等边三角形
*/
/*
题解：
tag：差分，排序
看到等边三角形，就可以考虑先排序
然后问的是最少要几次操作
我们先对数组做差分，然后找到 全局中最小的 del[i]+del[i+1] ，即为答案。
代码如下：
*/
inline void sensei()
{
int n;
cin >> n;
vector<int> a(n+1);
for(int i=1;i<=n;i++){
cin >> a[i];
}
vector<int> del(n+1);
sort(a.begin()+1,a.begin()+1+n);
for(int i=2;i<=n;i++){
del[i] = a[i] - a[i-1];
}
int ans=inf_ll;
for(int i=2;i<=n-1;i++){
int alls = del[i] + del[i+1];
ans = min(alls,ans);
}
cout << ans << endl;
}
signed main()
{
#ifndef LOCAL
fuckios
#endif
int t;
cin >> t;
while(t --){
sensei();
}
return 0;
}
T2. (Codeforces #822 DIV.2 ) B.Bright,Nice,Brilliant
/*
真的阅读理解，理解题面花了十多分钟，想题解只用了一两分钟
*/
/*
结论： 直接构造一下 除了最左和最右都是1，其他中间的都输出0即可（自己画一下图模拟一下就懂了，主要还是题难读懂）
*/
inline void sensei()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
if (i == 1) {
cout << "1" << endl;
continue;
} else if (i == 2) {
cout << "1 1" << endl;
continue;
}
for(int j=1;j<=i;j++){
if(j == 1 or j == i){
cout << "1 ";
}else{
cout << "0 ";
}
}
cout << endl;
}
}
signed main()
{
#ifndef LOCAL
fuckios
#endif
int t;
cin >> t;
while (t --) {
sensei();
}
return 0;
}
T3. (Codeforces round #822 Div.2) C.Removing Smallest Multiples
/*
题目大意：给你一个整数n，然后给出你一个长度为n的字符串s。
假定你有一个数组 a，a的内容即为 1，2，3，4……n。在这个字符串s中，某一位为0意味这要把这一位给删除掉，例如 n = 4， 1001，那么最终的a即为 1，4（2，3都没了）
现在你有一种操作，任意选定一个数字k
你可以在这个数组中删除k的最小倍数，同时你的消耗（cost） 增加 k
例如 a = [1,2,3,4]
k选定2，即可删除2，当2被删除了，假设你再次选中了2，那么此时最小倍数为4，删除4，总的消耗为 2+2 = 4
现在问，如果要让这个数组a里面只剩下字符串中对应 '1' 的位置，那么完成这个任务的最小消耗是多少？
*/
/*
题解：
用类似筛法的思想去枚举
并且使用一个布尔数组 st 记录一下某一位是否被删除掉了
详细见代码
*/
inline void sensei()
{
int n;
cin >> n;
string s;
cin >> s;
s = " " + s;
vector<bool> st(n+100);
int ans = 0;
int l=1;
int r=1;
int cnt = 1;
while(l <= n){
if(s[l*cnt] == '1'){
l++;
cnt = 1;
continue;
}
while(l*cnt <= n and s[l*cnt] == '0'){
if(!st[l*cnt]){
st[l*cnt] = true;
ans+=l;
cnt ++ ;
}else{
cnt++;
}
if(l*cnt > n ){
break;
}
}
l++;
cnt = 1;
}
cout << ans << endl;
}
signed main()
{
#ifndef LOCAL
fuckios
#endif
int t;
cin >> t;
while(t --) {
sensei();
}
return 0;
}
T4. (Codeforces Round #822 Div.2) D.Slime Escape
// 赛时没做出来，明天看别人的题解补一补
T5. (POJ - 1611) The Suspects
/*
题目大意：
现在要给小组成员分成m个组
每个小组成员有可能进入多个组
现在编号为0的成员身上带有病毒
问会有多少个成员最终中毒
*/
/*
题解，套一下并查集就可以了
另外，POJ是真的垃，一堆不支持的。
*/
int N,M;
struct DSU {
std::vector<int> f, siz;
DSU(int n) : f(n), siz(n, 1) { for(int i=0;i<n;i++) f[i]=i; }
int leader(int x) {
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
bool same(int x, int y) { return leader(x) == leader(y); }
bool merge(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) return false;
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) { return siz[leader(x)]; }
};
inline void sensei()
{
DSU dsu(N+1);
while(M -- ){
int allssz;
cin >> allssz;
vector<int> ids(allssz+1);
for(int i=1;i<=allssz;i++){
cin >> ids[i];
}
if(allssz <= 1) continue;
for(int i=2;i<=allssz;i++){
dsu.merge(ids[i],ids[i-1]);
}
}
cout << dsu.size(0) << endl;
}
signed main()
{
#ifndef LOCAL
fuckios
#endif
while(cin >> N >> M){
if(N == 0 and M == 0){
return 0;
}
sensei();
}
return 0;
}