洛谷 Likecloud-吃、吃、吃

题号：1508
感动哭，第一个自己不用想状态转移方程就写出来的动规超级简单题……我是有多辣鸡……
这样的题一天做20道都没问题啊，要是NOIP全考这个就好了（逃）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n, m;
int f[205][205],arr[205][205];
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> arr[i][j];
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
f[i][j] = max(max(f[i - 1][j], f[i - 1][j - 1]), f[i - 1][j + 1]) + arr[i][j];
}
}
cout << max(max(f[n][m / 2 + 1],f[n][m/2]),f[n][m/2+2]);
}

20180802更新：
呃呃呃。。。。因为之前做过这样的题所以才觉得很简单。。。。。。。。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int m, n;
int arr[205][205];
int main() {
memset(arr, 0x80, sizeof(arr));
cin >> m >> n;
for (int i = 1; i <= n; i++)arr[0][i] = 0;
arr[m+1][(n + 1) / 2] = 0;
for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)cin >> arr[i][j];
for (int i = m; i >= 0; i--) {
for (int j = 1; j <= n; j++) {
arr[i][j] += max(max(arr[i + 1][j - 1], arr[i + 1][j]), arr[i + 1][j + 1]);
}
}
int mmax = 0;
for (int i = 1; i <= n; i++) {
mmax = max(mmax, arr[0][i]);
}
cout << mmax;
}

洛谷 A*B Problem（高精度）

发表评论

题号：P1303

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstring>
#include<utility>
using namespace std;
int num1[5000], num2[5000], num3[5000];
char str1[5000], str2[5000];
int main(){
cin >> str1 >> str2;
if (str1[0] == '0' || str2[0] == '0'){
cout << 0;
return 0;
}
int len1 = strlen(str1) - 1, len2 = strlen(str2) - 1;
for (int i = len1; i >= 0; i--)num1[len1 - i + 1] = str1[i] - '0';
for (int i = len2; i >= 0; i--)num2[len2 - i + 1] = str2[i] - '0';
len1++;
len2++;
for (int i = 1; i <= len1; i++){
for (int j = 1; j <= len2; j++){
num3[i + j - 1] += num1[i] * num2[j];
}
}
int i;
for (i = 1; i<=len1+len2-1; i++){
num3[i + 1] += num3[i] / 10;
num3[i] %= 10;
}
for (int i = len1 + len2 - 1; i >= 1; i--){
cout << num3[i];
}
}

洛谷银河英雄传说

发表评论

题号：P1196
参见题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1196
结合源代码阅读才好……
推荐题解作者：作者: 超神火星人更新时间: 2017-04-29 09:14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstring>
#include<utility>
int father[30005],size[30005],front[30005];
using namespace std;
int sfind(int node){
if (father[node] == -1)return node;
int fn = sfind(father[node]);
front[node] += front[father[node]];
return father[node]=fn;
}
int main(){
for (int i = 1; i <= 30000; i++){
father[i] = -1;
size[i] = 1;
front[i] = 0;
}
ios::sync_with_stdio(false);
int n;
cin >> n;
while (n--){
char c;
int rf1, rf2;
cin >> c >> rf1 >> rf2;
int fa1 = sfind(rf1);
int fa2 = sfind(rf2);
switch (c){
case 'M':
front[fa1] += size[fa2];
father[fa1] = fa2;
size[fa2] += size[fa1];
size[fa1] = 0;
break;
case 'C':
if (fa1 != fa2)cout << "-1" << endl;
else cout << abs(front[rf1] - front[rf2])-1 << endl;
break;
}
}
}

20180815更新：
重做了这道题，还是看的这个人的题解。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include<iostream>
using namespace std;
int t;
int father[30005],front[30005],num[30005];
int _find(int node){
if(father[node]==0)return node;
int fn=_find(father[node]);
front[node]+=front[father[node]];
return father[node]=fn;
}
int main(){
ios::sync_with_stdio(false);
for(int i=1;i<=30000;i++)num[i]=1;
cin>>t;
while(t--){
char op;
int x,y;
cin>>op>>x>>y;
int fx=_find(x),fy=_find(y);
if(op=='M'){
front[fx]+=num[fy];
father[fx]=fy;
num[fy]+=num[fx];
num[fx]=0;
}else{
if(fx!=fy)cout<<-1<<endl;
else cout<<abs(front[x]-front[y])-1<<endl;
}
}
}

发现越到后面就越感觉是在抄题解怎么办，想也想不出来。

浴谷信息学夏令营 · 第一回正式结束！

发表评论

继续阅读 →

洛谷 [USACO1.5]数字三角形 Number Triangles

发表评论

题号：1216

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include<iostream>
#include<algorithm>
#include<string>
#define INF 2e9
using namespace std;
int n, arr[1005][1005];
int f[1005][1005];
int main(){
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= i; j++){
cin >> arr[i][j];
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= i; j++){
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + arr[i][j];
}
}
int m = 0;
for (int i = 1; i <= n; i++){
if (f[n][i] > m)m = f[n][i];
}
cout << m;
}

洛谷删数问题

发表评论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n;
string s;
int main(){
ios::sync_with_stdio(false);
cin >> s;
cin >> n;
for (int i = 0; i < s.length(); i++){
if (s[i]>s[i + 1]&&n>0){
s.erase(i, 1);
n--;
i=-1;//注意这里不是i--;因为有可能不符合顺序的数字出现在前面，需要重新返回头去找！
}
if (n == 0)break;
}
while (n--){
s.erase(s.length() - 1, 1);
}
while (s[0] == '0')s.erase(s.begin());
if(!s.empty())cout << s;
else cout << "0";
}

洛谷凌乱的yyy

发表评论

题号：1803
首先贴一种我一开始的错误做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct s{
int start;
int end;
bool operator < (s & s1){
if (end != s1.end)return end < s1.end;
else return start < s1.start;
}
}arr[1000005];
bool occupied[1000005];
int cnt;
int main(){
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end;
sort(arr + 1, arr + n + 1);
for (int i = 1; i <= n; i++){
if (!occupied[arr[i].start]){
for (int j = arr[i].start; j < arr[i].end; j++){
occupied[j] = true;
}
cnt++;
}
}
cout << cnt;
}

这里的21行条件判断是错的。为什么呢？仅判断比赛开头有空闲是不能保证后面的时间有空闲的。那么我写一个正确的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct s{
int start;
int end;
bool operator < (s & s1){
if (end != s1.end)return end < s1.end;
else return start > s1.start;
}
}arr[1000005];
int cnt;
int main(){
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end;
sort(arr + 1, arr + n + 1);
int t = 0;
for (int i = 1; i <= n; i++){
if (t<=arr[i].start){
cnt++;
t = arr[i].end;
}
}
cout << cnt;
}

这次的21行与之前的上一个比赛结束时间进行比较，如果在结束时间后面才能开始这个比赛。
注意：数组是排过序的，以结束时间、开始时间分别升序排序。

洛谷智力大冲浪

发表评论

题号：1230
一开始想排完序之后直接从前到后由时间1到时间n依次安排，这样做是不对的。
完全可以从一个任务的截止时间开始从后往前安排，哪里有空缺位置就放在那里。
一开始的想法忽略了其他任务也可以放在前面。（说的不太清楚）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<iostream>
#include<algorithm>
using namespace std;
int m, n;
struct s{
int t;
int w;
bool operator < (s & s1){
if (w != s1.w)return w>s1.w;
else return t < s1.t;
}
}arr[505];
bool occupied[505];
int main(){
ios::sync_with_stdio(false);
cin >> m >> n;
for (int i = 1; i <= n; i++){
cin >> arr[i].t;
}
for (int i = 1; i <= n; i++){
cin >> arr[i].w;
}
sort(arr + 1, arr + n + 1);
for (int i = 1; i <= n; i++){
if (!occupied[arr[i].t])occupied[arr[i].t] = true;
else{
bool flag = false;
for (int j = arr[i].t - 1; j >= 1;j--){
if (!occupied[j]){
occupied[j] = true;
flag = true;
break;
}
}
if (!flag)m -= arr[i].w;
}
}
cout << m;
}

洛谷关押罪犯

发表评论

题号：1525
参见题解：作者: 超级范范更新时间: 2017-07-23 17:05
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1525

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int father[40005];
struct s{
int u, v, w;
bool operator < (s & s1){
return w>s1.w;
}
}arr[100005];
int _find(int node){
if (father[node] == -1)return node;
return father[node] = _find(father[node]);
}
void merge(int x, int y){
x = _find(x);
y = _find(y);
if (x != y)father[x] = y;
}
bool sameset(int x, int y){
return _find(x) == _find(y);
}
int main(){
memset(father, -1, sizeof(father));
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> arr[i].u >> arr[i].v >> arr[i].w;
}
sort(arr + 1, arr + m + 1);
int maxw = 0;
for (int i = 1; i <= m; i++){
if (sameset(arr[i].u, arr[i].v)){
if (arr[i].w > maxw){
cout << arr[i].w;
return 0;
}
}
else{
merge(arr[i].u, arr[i].v + n);
merge(arr[i].v, arr[i].u + n);
}
}
cout << 0;
}

20180814更新：除了并查集做法还有二分图做法，应该也很好做，不写了。
题解：https://www.luogu.org/blog/Kesdiael3/solution-p1525

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct p{
int a,b,c;
bool operator < (const p& p2) const{
return c>p2.c;
}
}ps[100005];
int father[40005];
int _find(int x){
if(father[x]==0)return x;
return father[x]=_find(father[x]);
}
bool _union(int x,int y){
if(_find(x)==_find(y))return false;
father[_find(x)]=_find(y);
return true;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>ps[i].a>>ps[i].b>>ps[i].c;
sort(ps+1,ps+m+1);
for(int i=1;i<=m;i++){
if(_find(ps[i].a)==_find(ps[i].b)){
cout<<ps[i].c;
return 0;
}else{
_union(ps[i].a,ps[i].b+n);
_union(ps[i].b,ps[i].a+n);
}
}
cout<<0;
}

洛谷封锁阳光大学

发表评论

题号：1330
这个属于搜索中的染色问题，之前不会，以后要多多学习。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include<iostream>
#include<algorithm>
#include<list>
#include<queue>
using namespace std;
list<int> edge[100005];
int n, m;
int point[100005];
inline int color(int x){
if (x == 1)return 2;
else return 1;
}
int BFS(int i){
int cnter1 = 0, cnter2 = 0;
queue<pair<int, int>> q;
q.push(pair<int, int>(i, 1));
while (!q.empty()){
pair<int, int> cur = q.front(); q.pop();
if (point[cur.first] != 0){
if (point[cur.first] != cur.second)return -1;
continue;
}
point[cur.first] = cur.second;
if (cur.second == 1)cnter1++;
if (cur.second == 2)cnter2++;
for (auto iter = edge[cur.first].begin(); iter != edge[cur.first].end(); iter++){
q.push(pair<int, int>((*iter), color(cur.second)));
}
}
return cnter1 < cnter2 ? cnter1 : cnter2;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
int sum = 0;
for (int i = 1; i <= n; i++){
if (point[i] == 0){
int t=BFS(i);
if (t == -1){
cout << "Impossible";
return 0;
}
else
sum += t;
}
}
cout << sum;
}

20180806：基本上自己做出来了！！哈哈！有个小细节忽略了：是每个互不联通子图分别找出最小值加起来，不是整图统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, m;
vector<int> edges[10005];
int color[10005];
inline int getOppoColor(int x) {
if (x == 1)return 2;
else return 1;
}
int BFS(int s) {
int color1 = 0, color2 = 0;
queue<int> q;
color[s] = 1;
q.push(s);
while (!q.empty()) {
int node = q.front();
if (color[node] == 1)color1++;
else color2++;
q.pop();
for (int i = 0; i < edges[node].size(); i++) {
if (color[edges[node][i]] == 0) {
color[edges[node][i]] = getOppoColor(color[node]);
q.push(edges[node][i]);
}
else if (color[edges[node][i]] == color[node]) {
return 0;
}
}
}
return min(color1, color2);
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
}
int cnter = 0;
for (int i = 1; i <= n; i++) {
if (color[i] == 0 && edges[i].size() != 0) {
int cur = BFS(i);
if (cur == 0) {
cout << "Impossible";
return 0;
}
cnter += cur;
}
}

cout << cnter;
}

杰克部落

梦想本不会发光，发光的是追梦的你

洛谷 Likecloud-吃、吃、吃

洛谷 A*B Problem（高精度）

洛谷银河英雄传说

浴谷信息学夏令营 · 第一回正式结束！

洛谷 [USACO1.5]数字三角形 Number Triangles

洛谷删数问题

洛谷凌乱的yyy

洛谷智力大冲浪

洛谷关押罪犯

洛谷封锁阳光大学

2024 年 11 月
一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30