本文主要是介绍Codeforces Round #338 (Div. 2) 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
所以苟蒻万年不做E。。。
A：
Vasya wants to turn on Christmas lights consisting of m bulbs. Initially, all bulbs are turned off. There are n buttons, each of them is connected to some set of bulbs. Vasya can press any of these buttons. When the button is pressed, it turns on all the bulbs it's connected to. Can Vasya light up all the bulbs?
If Vasya presses the button such that some bulbs connected to it are already turned on, they do not change their state, i.e. remain turned on.
The first line of the input contains integers n and m (1 ≤ n, m ≤ 100) — the number of buttons and the number of bulbs respectively.
Each of the next n lines contains xi (0 ≤ xi ≤ m) — the number of bulbs that are turned on by the i-th button, and then xi numbers yij(1 ≤ yij ≤ m) — the numbers of these bulbs.
If it's possible to turn on all m bulbs print "YES", otherwise print "NO".
3 4 2 1 4 3 1 3 1 1 2
YES
3 3 1 1 1 2 1 1
NO
In the first sample you can press each button once and turn on all the bulbs. In the 2 sample it is impossible to turn on the 3-rd lamp.
题意：
有n个开关和m个灯泡
每个开关按下后对应一些灯泡就会亮起来，而如果那些灯泡本来就是亮的那么不会改变状态
思路：
全部按一遍。。。随意模拟之
#include<iostream>
#include<cstdio>
#include<windows.h>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;const int maxn = 110;bool L[maxn];
int n,m,i,j;int main()
{#ifdef YZYfreopen("yzy.txt","r",stdin);#endifcin >> n >> m;memset(L,0,sizeof(L));for (i = 1; i <= n; i++) {scanf("%d",&j);while (j--) {int x;scanf("%d",&x);L[x] = 1;}}for (i = 1; i <= m; i++)if (!L[i]) {printf("NO");return 0;}printf("YES");return 0;
}
This Christmas Santa gave Masha a magic picture and a pencil. The picture consists of n points connected by m segments (they might cross in any way, that doesn't matter). No two segments connect the same pair of points, and no segment connects the point to itself. Masha wants to color some segments in order paint a hedgehog. In Mashas mind every hedgehog consists of a tail and some spines. She wants to paint the tail that satisfies the following conditions:
- Only segments already presented on the picture can be painted;
- The tail should be continuous, i.e. consists of some sequence of points, such that every two neighbouring points are connected by a colored segment;
- The numbers of points from the beginning of the tail to the end should strictly increase.
Masha defines the length of the tail as the number of points in it. Also, she wants to paint some spines. To do so, Masha will paint all the segments, such that one of their ends is the endpoint of the tail. Masha defines the beauty of a hedgehog as the length of the tail multiplied by the number of spines. Masha wants to color the most beautiful hedgehog. Help her calculate what result she may hope to get.
Note that according to Masha's definition of a hedgehog, one segment may simultaneously serve as a spine and a part of the tail (she is a little girl after all). Take a look at the picture for further clarifications.
First line of the input contains two integers n and m(2 ≤ n ≤ 100 000, 1 ≤ m ≤ 200 000) — the number of points and the number segments on the picture respectively.
Then follow m lines, each containing two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the numbers of points connected by corresponding segment. It's guaranteed that no two segments connect the same pair of points.
Print the maximum possible value of the hedgehog's beauty.
8 6 4 5 3 5 2 5 1 2 2 8 6 7
9
4 6 1 2 1 3 1 4 2 3 2 4 3 4
12
The picture below corresponds to the first sample. Segments that form the hedgehog are painted red. The tail consists of a sequence of points with numbers 1, 2 and 5. The following segments are spines: (2, 5), (3, 5) and (4, 5). Therefore, the beauty of the hedgehog is equal to 3·3 = 9.
题意：
Masha 有一张n个点m条边的图有如下几种定义：
1.刺猬：
由一些点构成，包括一条尾巴和刺，当然他有一个中心，如例图中的5号点
2.刺：
每个点的刺的数量等于它的度数
3.尾巴：
由某个点到刺猬中心的路径上的所有点，尾巴大小等于点的数量
并且尾巴上的点的编号必须严格递增
问：
任选一个点做刺猬的中心，该刺猬的刺的数量*尾巴大小的最大值是多少？
思路：
对于刺，维护度数即可
对于尾巴长度，每给出一条边就把它想成从编号小的点连向编号大的点的有向边，让编号大的点的入度+1。显然这样做的图不存在环！
那么只需对原图进行一次拓扑排序，维护当前到这个点能够成的最长尾巴长度，就能统计出来啦
注：尾巴长度可以等于1。。。苟蒻真是英语太差。。。
#include<iostream>
#include<cstdio>
#include<windows.h>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;const int maxn = 1E5 + 10;int L[maxn],d[maxn],s[maxn],n,m;
bool vis[maxn];vector <int> v[maxn];
queue <int> q;void BFS(int u)
{q.push(u);while (!q.empty()) {int k = q.front(); q.pop();for (int l = 0; l < v[k].size(); l++) {int to = v[k][l];--d[to];if (to < k) continue;vis[to] = 1;L[to] = max(L[to],L[k] + 1);if (!d[to]) q.push(to);}}
}int main()
{#ifdef YZYfreopen("yzy.txt","r",stdin);#endifcin >> n >> m;while (m--) {int x,y;scanf("%d%d",&x,&y);++d[max(x,y)];++s[x]; ++s[y];v[x].push_back(y);v[y].push_back(x);}memset(L,0,sizeof(L));memset(vis,0,sizeof(vis));for (int i = 1; i <= n; i++)if (!vis[i]) {L[i] = 1; vis[i] = 1;BFS(i);}long long ans = 0;for (int i = 1; i <= n; i++) //if (L[i] > 1) ans = max(ans,1LL*L[i]*1LL*s[i]);cout << ans;return 0;
}A boy named Ayrat lives on planet AMI-1511. Each inhabitant of this planet has a talent. Specifically, Ayrat loves running, moreover, just running is not enough for him. He is dreaming of making running a real art.
First, he wants to construct the running track with coating t. On planet AMI-1511 the coating of the track is the sequence of colored blocks, where each block is denoted as the small English letter. Therefore, every coating can be treated as a string.
Unfortunately, blocks aren't freely sold to non-business customers, but Ayrat found an infinite number of coatings s. Also, he has scissors and glue. Ayrat is going to buy some coatings s, then cut out from each of them exactly one continuous piece (substring) and glue it to the end of his track coating. Moreover, he may choose to flip this block before glueing it. Ayrat want's to know the minimum number of coating s he needs to buy in order to get the coating t for his running track. Of course, he also want's to know some way to achieve the answer.
First line of the input contains the string s — the coating that is present in the shop. Second line contains the string t — the coating Ayrat wants to obtain. Both strings are non-empty, consist of only small English letters and their length doesn't exceed 2100.
The first line should contain the minimum needed number of coatings n or -1 if it's impossible to create the desired coating.
If the answer is not -1, then the following n lines should contain two integers xi and yi — numbers of ending blocks in the corresponding piece. If xi ≤ yi then this piece is used in the regular order, and if xi > yi piece is used in the reversed order. Print the pieces in the order they should be glued to get the string t.
abc cbaabc
2 3 1 1 3
aaabrytaaa ayrat
3 1 1 6 5 8 7
ami no
-1
In the first sample string "cbaabc" = "cba" + "abc".
In the second sample: "ayrat" = "a" + "yr" + "at".
题意：
Ayrat想做一个字符串问题。。。
现有一个串a还有一个串b
每次能得到一个串a，从中选取一个子串(可以把a翻转然后再取)把它接在之前拼的串后面，最终要得到串b
问最少需要几个串a？？？
思路：
显然dp
f[i] = min(f[j]+1) 该方程可行条件当b串[j+1,i]位置是a的子串
如果能O(1)判断是不是的话就能O(n^2)解决了！
那么将a串的所有子串都扔进一个trie，每个子串长度为n,一共有n^2个子串。。。
所以空间复杂度是O(n^3)
所以因为算错空间复杂度纠结了十几分钟。。。。。。。。。。
可以想象一开始从位置1到位置strlen(b)，每次固定起点，右指针从左往右扫一遍就把所有以i为起点的子串扔进trie了，这样做每次消耗空间O(n)，所以总的空间复杂度O(n^2)
dp过程就简单了！
注：
烧空间大小一开始没算好，然后打的时候没注意小写英文字母问题，所有'a'打成'A'。。。。。。
#include<iostream>
#include<cstdio>
#include<windows.h>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;const int maxn = 2110;
const int INF = 10000;struct T{int s[26];short l,r;
}trie[maxn*maxn];char a[maxn],b[maxn];
int cur = 0,n,m,f[maxn],fa[maxn],l[maxn],r[maxn];void b1(int i)
{int now = 0;int x = i;for (; i <= n; i++) {if (!trie[now].s[a[i]-'a']) trie[now].s[a[i]-'a'] = ++cur;now = trie[now].s[a[i]-'a'];trie[now].l = x;trie[now].r = i;}
}void b2(int i)
{int now = 0;int x = i;for (; i > 0; i--) {if (!trie[now].s[a[i]-'a']) trie[now].s[a[i]-'a'] = ++cur;now = trie[now].s[a[i]-'a'];trie[now].l = x;trie[now].r = i;}
}void P(int k)
{if (!fa[k]) {cout << l[k] << ' ' << r[k] << endl;return;}P(fa[k]);cout << l[k] << ' ' << r[k] << endl;
}int main()
{#ifdef YZYfreopen("yzy.txt","r",stdin);#endifscanf("%s",1+a);scanf("%s",1+b);n = m = 0;for (int i = 1; a[i] >= 'a' && a[i] <= 'z'; i++,n++);for (int i = 1; b[i] >= 'a' && b[i] <= 'z'; i++,m++);for (int i = 1; i <= n; i++) b1(i);for (int i = n; i > 0; i--) b2(i);for (int i = 1; i <= m; i++) f[i] = INF;f[0] = 0;for (int i = 1; i <= m; i++) {int now = 0;for (int j = i; j > 0; j--) {if (trie[now].s[b[j]-'a']) {now = trie[now].s[b[j]-'a'];if (f[i] > f[j-1] + 1) {f[i] = f[j-1] + 1;l[i] = trie[now].r;r[i] = trie[now].l;fa[i] = j-1;}}else break;}}if (f[m] == INF) cout << -1;else {cout << f[m] << endl;P(m); }return 0;
}
给n个质数，记x 为他们的乘积
问x所有因数的乘积是多少
思路：
场内做到这题时只剩5min了。。。。。
然而全是没学过的数学知识。。。
1.
一个数x记分解质因数后有
x = p1^a1*p2^a2*p3^a3*...*pn^an
则它的因数个数为f(x) = (a1+1)*(a2+1)*(a3+1)*...*(an+1)
2.费马小定理
a^(m-1) ≡ 1(mod m) ==> a^x ≡ a^(x%(m-1)) (mod m)
当m是素数且a != 0。。。
对于某非完全平方数x，由于因数总是成对出现，于是可以把他们两两配对
于是 ans = x^(f(x)/2)
反之，因数会多出一个可爱的根号x
于是 ans = x^((f(x)-1)/2)*根号x
显然可以通过质因数个数判断该x是否为完全平方数
如果是，那么x因数个数必为奇数，mod 10E9+6后还是奇数 所以可以通过取余结束强行除以2来确定x的指数 然后根号x就是一半质因数乘起来
反之，可以在统计f(x)过程任取ai%2 == 1,在这个地方先除以2
综上，因为2在模10E9+6系里面无法求出逆元来着。。。
所以用一些投机取巧的办法(codeforces上的题解真心看不懂。。。。。)
#include<iostream>
#include<cstdio>
#include<windows.h>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;const int maxn = 2E5 + 20;
typedef long long LL;
const LL mo = 1000000007;LL p = 1,x = 1,ans = 1,y = 1,tot = 1;
int num[maxn],n;LL ksm(LL a,LL b)
{LL ret = 1;for (; b; b >>= 1) {if (b & 1) ret = ret * a % mo;a = a*a%mo;}return ret%mo;
}int main()
{#ifdef YZYfreopen("yzy.txt","r",stdin);#endifcin >> n;for (int i = 1; i <= n; i++) {int j;scanf("%d",&j);++num[j];}int flag = 1;for (int i = 2; i <= 200000; i++)if (num[i]) {x = x*ksm(i,num[i]/2)%mo;if (num[i] % 2 == 1 && flag) {p = p*(1LL*(num[i]+1)/2LL) % (mo-1LL);flag = 0;}else {p = p*1LL*(num[i]+1)%(mo-1);}tot = tot*ksm(i,num[i])%mo;}if (flag) p /= 2,ans = ans*x%mo;ans = ans*ksm(tot,p)%mo;cout << ans;return 0;
}
这篇关于Codeforces Round #338 (Div. 2) 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
