// 我的第1题AC代码
#include <iostream>
#include <vector>
using namespace std;
int M, N, P = 0, Q = 0;
void search(vector<vector<int>> &G, int i, int j, int &Max) {
if (i < 0 || i >= M || j < 0 || j >= N)
return;
if (G[i][j] == 1) {
G[i][j] = 0; Max += 1;
search(G, i - 1, j, Max); search(G, i + 1, j, Max);
search(G, i, j - 1, Max); search(G, i, j + 1, Max);
search(G, i - 1, j + 1, Max); search(G, i + 1, j - 1, Max);
search(G, i - 1, j - 1, Max); search(G, i + 1, j + 1, Max);
}
}
int main()
{
scanf("%d,%d", &M, &N);
vector<vector<int>> G(M, vector<int>(N));
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
scanf("%d,", &G[i][j]);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (G[i][j] == 1) {
int Max = 0; P++;
search(G, i, j, Max);
if (Max > Q) Q = Max;
}
}
}
cout << P << "," << Q;
return 0;
}
// 我的第2题AC代码
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct region {
int l, r;
};
region str2region(const string &s) {
struct region res;
int a = s.find(',');
res.l = stoi(s.substr(0, a));
res.r = stoi(s.substr(a + 1, s.length() - 1));
return res;
}
struct compare {
bool operator() (region a, region b) {
if (a.l != b.l)
return a.l < b.l;
else
return a.r < b.r;
}
};
int main() {
int m, a;
string s, r;
vector<region> regions;
cin >> m;
for (int i = 0; i < m; ++i) {
cin >> s;
while ((a = s.find(';')) != -1) {
r = s.substr(0, a);
s = s.substr(a + 1, s.length() - 1);
regions.push_back(str2region(r));
}
regions.push_back(str2region(s));
}
sort(regions.begin(), regions.end(), compare());
for (int i = 0; i < regions.size() - 1; ++i) {
if (regions[i].r >= regions[i + 1].l) {
regions[i].r = regions[i + 1].r;
regions.erase(regions.begin() + i + 1);
--i;
}
}
int i;
for (i = 0; i < regions.size() - 1; ++i)
cout << regions[i].l << ',' << regions[i].r << ';';
cout << regions[i].l << ',' << regions[i].r << endl;
return 0;
}
// 我的第5题AC代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Anchor {
int s, e;
};
struct compare {
bool operator() (Anchor a, Anchor b) {
if (a.e != b.e)
return a.e < b.e;
else
return a.s < b.s;
}
};
int main() {
int N, M, res = 0, curr = 0;
cin >> N >> M;
Anchor anchor;
vector<Anchor> anchors;
for (int i = 0; i < N; ++i) {
cin >> anchor.s >> anchor.e;
if (anchor.e < anchor.s && anchor.e == 0)
anchor.e += N;
if (anchor.e >= anchor.s)
anchors.push_back(anchor);
}
sort(anchors.begin(), anchors.end(), compare());
for (int i = 0; i < anchors.size(); ++i) {
if (curr <= anchors[i].s) {
res++;
curr = anchors[i].e;
}
}
cout << res << endl;
return 0;
}
// 第3题20% 哎 - -~!浪费了太多时间
/* 我的思路是转换成0-1背包问题的，先取若干张卡，然后用canDivide判断这些卡片
* 能不能被分为和相等的两组，我的直觉感觉我的canDivide有问题，时间紧没有去推导
* 然后canDivide传入的参数已经从大到小排列了的。
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Card {
int person;
int group;
};
struct compare {
bool operator() (Card a, Card b) {
if (a.person != b.person)
return a.person > b.person;
else
return a.group > b.group;
}
};
bool canDivide(const vector<Card> &cards) {
int res = 0, i;
for (i = 0; i < cards.size(); i++) {
if (res > 0)
res -= cards[i].person;
else
res += cards[i].person;
}
return res == 0;
}
int sumCard(const vector<struct Card> &cards) {
int i;
int sum = 0;
for (int i = 0; i < cards.size(); i++)
sum += cards[i].group;
return sum;
}
int bag(const vector<Card> &cards, vector<Card> curr, int i) {
if (i == cards.size()) {
if (canDivide(curr))
return sumCard(curr);
else
return 0;
}
else {
int a = bag(cards, curr, i + 1);
curr.push_back(cards[i]);
int b = bag(cards, curr, i + 1);
return a > b ? a : b;
}
}
int main() {
int n;
vector<Card> cards, curr;
Card card;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> card.person >> card.group;
cards.push_back(card);
}
sort(cards.begin(), cards.end(), compare());
cout << bag(cards, curr, 0) << endl;
return 0;
}
// 第3题最后没时间了，投机取巧拿了40%
#include <cstdio>
using namespace std;
int main() {
int n;
scanf("%d", &n);
int sum = 0;
for(int i = 0; i < n; ++i) {
int a, b;
scanf("%d %d", &a, &b);
sum += b;
}
printf("%d", sum);
}
// 第4题60% 哎 - -~! 不想说啥了，***难受~！ 代码就不发了,惭愧~！！！
