Educational Codeforces Round 78 (Rated for Div. 2)

题意：给定s1，s2两个字符串。问s2中是否有s1不计顺序的字串。

题解：sort就完事了，比较一下就好。

贴dalao代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main() {
 4     int t;
 5     cin >> t;
 6     while (t--) {
 7         string s1, s2;
 8         cin >> s1 >> s2;
 9         sort(s1.begin(), s1.end());
10         string ans = "NO";
11         for (int i = 0; i + s1.size() <= s2.size(); ++i) {
12             auto d = s2.substr(i, s1.size());
13             sort(d.begin(), d.end());
14             if (s1 == d) {
15                 ans = "YES";
16                 break;
17             }
18         }
19         cout << ans << "
";
20     }
21     return 0;
22 }

B - A and B

题意：给定两个数字，可以进行操作，给其中一个数+1，下次给其中一个数+2，以此类推，求最小操作数。

题解：num为abs两数之差，转化为可对num操作，加一或减一，加二或减二...

　　　考虑在1,2，...n每个数前面加正号或负号，所得最大的数为n*(n+1)/2，显然num必须小于n*(n+1)/2,

　　　考虑改变1，2..n某个数k前的符号，总的结果会改变2*k，所以通过改变符号可以遍历-n*(n+1)/2到n*(n+1)/2中所有奇偶性和n*(n+1)/2相同的数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t,a,b;
 4 int main()
 5 {
 6     cin>>t;
 7     while(t)
 8     {
 9         t--;
10         cin>>a>>b;
11         int num=abs(a-b);int ans=0;
12         while(ans*(ans+1)/2<num||(ans*(ans+1)/2-num)%2)
13         ans++;
14         cout<<ans<<endl;
15     }
16 }

C - Berry Jam

题意：给定2*n个12序列，从n和n+1之间可以任意往左和往右删除任意长度，使得剩下的12个数相等，求min删除个数。

题解：考虑贡献，维护一个前缀和，1的贡献为1,2为-1，删除左边部分的前缀和和右边的后缀和为相反数即可。

　　　维护一个pos数组，pos【i】表示前缀和为i的位置。

　　　然后我们从n位置开始枚举就可以了，查找可以用map（stl大法好）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t,n;
 4 int pre[300000];
 5 int main()
 6 {
 7     cin>>t;
 8     while(t--)
 9     {
10         cin>>n;int a;map<int,int>pos;
11         pos[0]=0;
12         for(int i=1;i<=2*n;i++)
13         {
14             cin>>a;pre[i]=pre[i-1]+(a==1?1:-1);
15             if(i<=n)pos[pre[i]]=i;
16         }
17         int ans=2*n;
18         for(int i=n;i<=2*n;i++)
19         {
20             map<int,int>::iterator it=pos.find(pre[i]-pre[n*2]);    
21             if(it!=pos.end()) ans=min(ans,i-it->second);
22         }
23         cout<<ans<<endl;
24     }
25 }

D.Segment Tree

题意：给定n个区间，i点和j点连接当且仅当区间i和区间j有交集且其中一个不被另一个完全包括。问是否能组成树。

题解：判断是否连了n-1条边。用并查集维护，如果合并前二者已在一个集合，则连成了环。

　　　问题就在于如何判断两个点是否相连。

　　　暴力n^2枚举，5*1e5就算是2s也是tle的死死的。

　　　可以按左端点排序，开一个set维护右端点，二分查找大于等于当前左端点的set元素，然后往后看，大于当前右节点就退出，否则合并，最后把当前右节点插进去。

　　详见代码。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 int f[2*600000];
 5 int find(int x){return f[x]==x?x:find(f[x]);}
 6 void merge(int x,int y){f[find(x)]=f[find(y)];}
 7 struct data{int l,r;}a[600000];
 8 bool cmp(data a,data b){return a.l<b.l;}
 9 set<int> s;
10 int main()
11 {
12     scanf("%d",&n);int ent=0;
13     for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r),f[i]=i,f[i+n]=i+n;
14     sort(a+1,a+1+n,cmp);
15     for(int i=1;i<=n;i++)
16     {
17         set<int>::iterator it=s.lower_bound(a[i].l);
18         for(;it!=s.end()&&*it<a[i].r;it++)
19         {
20             if(find(*it)==find(a[i].r))return !printf("NO
");
21             merge(*it,a[i].r);
22             ent++;
23         }
24         s.insert(a[i].r);
25     }
26     ent==n-1?cout<<"YES":cout<<"NO";
27     return 0;
28 }

后面的回头再补