1003
题意：Bi=maxi∤jAj , i≥2. 给出Ai，求出所有Bi
思路：直接暴力了，存储Ai和i，然后按Ai从小到大排序，然后从求出每个位置不整除i对应的最大数，在1e5的范围内最多会找100次(这个可以去看看反素数表，1e5的范围内一个数因子最多的个数就是100个，好像是这么多，根据鸽笼原理就是这样咯)，最后的复杂度就是O(100 * n)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b) memset(a, b, sizeof a)
#define REP(i, x, n) for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
struct Node {
int val, id;
bool operator < (const Node &a) {
return val > a.val;
}
}node[qq];
int n;
int main(){
int t; scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", &node[i].val);
node[i].id = i + 1;
}
sort(node, node + n);
for(int i = 2; i <= n; ++i) {
for(int j = 0; j < n; ++j) {
if(node[j].id % i != 0) {
printf("%d", node[j].val);
printf(i == n ? "\n" : " ");
break;
}
}
}
}
return 0;
}
1008
题意：给出一个m，一个串，在其中选择两个不相交的字串使得disA,B=∑i=0n−1|Ai−Bn−1−i| 小于等于m，问字串最长是多大
思路：想了很久猜想出来这个题的解法，假设两个串A、B，A串对应的位置是a c， B串对应的位置是b d，假设a < b，可以发现在范围a - d中，两个串是关于中间对称的，所以我想到了枚举对称轴，然后使用尺取法来维护串最大的长度
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b) memset(a, b, sizeof a)
#define REP(i, x, n) for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 2e5 + 10;
const int INF = 1e9 + 10;
char st[5005];
int n, m, res;
int main(){
int t; scanf("%d", &t);
while(t--) {
scanf("%d", &m);
scanf("%s", st + 1);
n = strlen(st + 1);
res = 0;
for(int k = 1; k < n; ++k) {
int a = k, b = k + 1;
int c = k, d = k + 1;
int sum = 0;
while(a != 0 && b != n + 1) {
sum += abs(st[a] - st[b]);
while(sum > m) {
sum -= abs(st[c] - st[d]);
c--, d++;
}
res = max(res, c - a + 1);
--a, ++b;
}
a = k, b = k + 2;
c = k, d = k + 2;
sum = 0;
while(a != 0 && b != n + 1) {
sum += abs(st[a] - st[b]);
while(sum > m) {
sum -= abs(st[c] - st[d]);
c--, d++;
}
res = max(res, c - a + 1);
--a, ++b;
}
}
printf("%d\n", res);
}
return 0;
}
1010
题意：给出n个点，n - 1条边， pi的父结点是i + 1，现在两个人玩游戏Alice先手，Bob后手，最初结点都是没有颜色的， 玩家Alice只可以选择一个没有颜色的点将它涂为白色，玩家Bob可以选择一个没有颜色的点将它涂为黑色，并且与这个点有边的点都会被涂为黑色(无论它之前是白色还是没有颜色)， 玩家Bob由于冲了VIP，所以他有k次机会，可以在游戏中任意时刻去消除一条边，给出这个图，问最终谁会赢
思路：其实首先要明白一点这个k在什么情况下会使用，最开始推整个图是一条链的情况，发现只有n = 2时Bob才会赢，之后就画了几颗奇怪的图发现确实是这样，就猜了猜是不是把图都变成多个结点树为2的子图Bob就能赢，然后就试了试直接Dfs进行标记，搜到底的时候判断一些这点和它的父结点是否被标记，首先判断能不能变成多个结点数为2的子图，然后再判断需要消边的次数是不是小于等于k
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b) memset(a, b, sizeof a)
#define REP(i, x, n) for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 2e5 + 10;
const int INF = 1e9 + 10;
vector<int> G[505];
int n, k;
int cnt;
bool vis[505];
void Init() {
for(int i = 0; i <= n; ++i) {
G[i].clear();
}
mst(vis, false);
}
bool f;
void Dfs(int u, int fa) {
for(int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if(v == fa) continue;
Dfs(v, u);
}
if(!vis[u] && u != 1 && !vis[fa]) vis[u] = vis[fa] = true;
}
int main(){
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &k);
Init();
for(int i = 2; i <= n; ++i) {
int x; scanf("%d", &x);
G[x].pb(i), G[i].pb(x);
}
f = true, cnt = 0;
Dfs(1, -1);
for(int i = 1; i <= n; ++i) {
if(!vis[i]) f = false;
}
if(f && n / 2 - 1 <= k) {
puts("Bob");
} else {
puts("Alice");
}
}
return 0;
}
1011
trick 有点疯狂阿、
自己写了两发WA掉了，队友一改就tm对了
题意：有三门课程，给出n个班级选择A课程人数，B课程人数，C课程人数，AB课程人数，BC课程人数，AC课程人数以及ABC课程人数，让你求一个所有班级中参加课程的人数最多的是多少，其中某些班级的数据有错误，可以忽略掉这个班级，保证至少有意组数据正确
思路：先判一下，求出答案后反判一下可以看下这组数据
5 5 5 5 5 5 0
这肯定是不对的
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define mst(a, b) memset(a, b, sizeof a)
#define REP(i, x, n) for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 2e5 + 10;
const int INF = 1e9 + 10;
int num[105][10];
int main(){
int t; scanf("%d", &t);
while(t--) {
int n; scanf("%d", &n);
int maxn = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= 7; ++j) {
scanf("%d", &num[i][j]);
}
if(num[i][4] > min(num[i][1], num[i][2])) continue;
if(num[i][5] > min(num[i][2], num[i][3])) continue;
if(num[i][6] > min(num[i][1], num[i][3])) continue;
if(num[i][7] > min(num[i][4], min(num[i][5], num[i][6]))) continue;
int ans = 0;
for(int j = 1; j <= 7; ++j) {
if(j >= 4 && j <= 6) ans = ans - num[i][j];
else ans = ans + num[i][j];
}
if(ans - num[i][1] - num[i][2] + num[i][4] < 0) continue;
if(ans - num[i][2] - num[i][3] + num[i][5] < 0) continue;
if(ans - num[i][1] - num[i][3] + num[i][6] < 0) continue;
if(ans - num[i][4] - num[i][5] - num[i][6] + num[i][7] * 2 < 0) continue;
maxn = max(maxn, ans);
}
printf("%d\n", maxn);
}
return 0;
}