A - Equally (abc385 A)
题目大意
给定三个数，问能不能分成两个以上的组，使其和相同。
解题思路
两个以上的组要么是两组要么是三组，三组就是三个数都相等，两组就是两个小的加起来等于大的。
代码
void solve()
{
int a[10];
cin >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
if ((a[0] == a[1] && a[1] == a[2]) || (a[0] + a[1] == a[2]))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
B - Santa Claus 1 (abc385 B)
题目大意
给定一个二维地图，#是墙，.是空地，@是房间。
给定起点和每一步的操作序列，如果可以走就走，如果撞墙了就原地不动，问最后的位置和一共经过了几个房间，经过相同的房间只算一次。
解题思路
按照题意模拟即可
代码
void solve()
{
string s[104];
int h, w, x, y;
cin >> h >> w >> x >> y;
for(int i=0;i<h;i++) cin >> s[i];
map<char, int> dx, dy;
dx['U'] = -1, dx['D'] = 1, dx['L'] = 0, dx['R'] = 0;
dy['U'] = 0, dy['D'] = 0, dy['L'] = -1, dy['R'] = 1;
string t;
cin >> t;
int ans = 0;
for(auto i : t) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > h || ny < 1 || ny > w || s[nx - 1][ny - 1] == '#') {
continue;
}
if (s[nx - 1][ny - 1] == '@') {
ans++;
s[nx - 1][ny - 1] = '.';
}
x = nx, y = ny;
}
cout << x << " " << y << " " << ans;
}
C - Illuminate Buildings (abc385 C)
题目大意
给定一个数组，问最多选几个位置，使这几个位置的数相同，并且位置之间间隔相同。
解题思路
枚举，首先枚举间隔，然后枚举起点（起点的范围在间隔以内），然后从起点向后遍历，就是在求最长的一段相同的数字有多长，那么记录一个长度，如果当前数字和上一个相同就加一，否则清空，然后每次都更新一下ans即可。
代码
void solve()
{
int n;
cin >> n;
vi a(n);
rep(i, n) cin >> a[i];
int tmp = 1;
for (int k = 1;k < n;k++) {
for (int i = 0;i < k;i++) {
int lst = 1;
for (int j = i + k;j < n;j += k) {
if (a[j] == a[j - k]) lst++;
else lst = 1;
tmp = max(tmp, lst);
}
}
}
cout << tmp;
}
D - Santa Claus 2 (abc385 D)
题目大意
与第二题类似，但没有墙壁。
一共给定N个房间的坐标，以及M条指令，每条指令是向上下左右某个方向前进C步，问最后的坐标以及经过了多少个房间，重复的房间依然只算一个。
解题思路
用两个map套set，记录某个x坐标内有哪些房间和某个y坐标内有哪些房间。
那么分两种情况，一种是上下走，那么他会删除当前x坐标内的连续一段y坐标的房间，在这个x坐标的set内upperbound和lowerbound出这一段y坐标的范围，然后在两个map中删掉这些走过的房间就可以了。
代码
#define int long long
#define rep(i,n) for(int i=0;i<(int)(n);i++)
void solve()
{
int n, m;
int sx, sy;
cin >> n >> m >> sx >> sy;
map<int, set<int> > mx, my;
rep(i, n) {
int x, y;
cin >> x >> y;
mx[x].insert(y);
my[y].insert(x);
}
map<char, int> dx, dy;
dx['U'] = 0, dx['D'] = 0, dx['L'] = -1, dx['R'] = 1;
dy['U'] = 1, dy['D'] = -1, dy['L'] = 0, dy['R'] = 0;
int x = sx, y = sy;
rep(tt, m) {
char d;
int c;
cin >> d >> c;
int nx = x + dx[d] * c;
int ny = y + dy[d] * c;
if (d == 'U' || d == 'D') {
if (!mx.count(nx)) {
x = nx;
y = ny;
continue;
}
int st = y, ed = ny;
if (st > ed) swap(st, ed);
auto l = mx[nx].lower_bound(st);
auto r = mx[nx].upper_bound(ed);
if (r == mx[nx].begin()) {
x = nx;
y = ny;
continue;
}
vi v;
for (auto i = l; i != r; i++) {
v.pb(*i);
}
for (auto i : v) {
mx[x].erase(i);
if (my.count(i)) my[i].erase(nx);
}
}
if (d == 'L' || d == 'R') {
if (!my.count(ny)) {
x = nx;
y = ny;
continue;
}
int st = x, ed = nx;
if (st > ed) swap(st, ed);
auto l = my[ny].lower_bound(st);
auto r = my[ny].upper_bound(ed);
if (r == my[ny].begin()) {
x = nx;
y = ny;
continue;
}
vi v;
for (auto i = l; i != r; i++) {
v.pb(*i);
}
for (auto i : v) {
my[y].erase(i);
if (mx.count(i)) mx[i].erase(ny);
}
}
x = nx;
y = ny;
}
int sum = 0;
for (auto i : mx) sum += i.second.size();
cout << x << " " << y << " " << n - sum;
}
E - Snowflake Tree (abc385 E)
题目大意
一个雪花图的生成是选定一个x和y，首先在一个点上连x个点，然后在这x个点上连y个叶子。
现在给定一棵树，问最多删除多少个点可以将其变成一个雪花图。
解题思路
反过来想就是找一颗最大的雪花图，我们枚举每一个点作为雪花图的根，然后肯定是要数一下儿子都有多少孙子，先把这个存进一个数组里，那么现在问题就是求可以使数组里的某个数减一，减到0数就会消失，问每个数相同的情况下最大的和是多少。
不难想到最后每个数相同肯定也是等于其中某个数，就是有一个数是不动的，比该数大的-1，比该数小的直接删除，那么就可以排个序，枚举这个数是谁，然后直接乘出来了。
代码
#define N 300010
int n,ans=0;
vector<int> vt[N];
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
x--,y--;
vt[x].push_back(y);
vt[y].push_back(x);
}
for(int i=0;i<n;i++){
vector<int> seq;
for(auto x:vt[i]) seq.push_back(vt[x].size()-1);
sort(seq.begin(),seq.end());
reverse(seq.begin(),seq.end());
for(int j=0;j<seq.size();j++) if(seq[j]) ans=max(ans,(j+1)*(seq[j]+1)+1);
}
printf("%d\n",n-ans);
return 0;
}