比赛链接：http://acm-software.hrbust.edu.cn/contest.php?cid=1082
A.好SB啊真是，还以为lis…数有多少个数不一样。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int maxn = ;
int ret;
int n;
set<int> s;
int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
int x;
s.clear();
ret = ;
for(int i = ; i < n; i++) {
scanf("%d", &x);
if(s.find(x) == s.end()) {
ret++;
s.insert(x);
}
}
printf("%d\n", ret);
}
return ;
}
B.顺着求和就行。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int maxn = ;
LL ret;
char s[maxn]; int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
scanf("%s", s);
ret = ;
for(int i = ; s[i]; i++) {
ret += s[i] - 'A' + ;
}
cout << ret << endl;
}
return ;
}
C.折半1000-9999，然后对称过来。注意前导零。
#include <bits/stdc++.h>
using namespace std; typedef long long LL; int main() {
// freopen("in", "r", stdin);
for(LL i = ; i <= ; i++) {
printf("%d", i);
int y = ;
int t = i;
int cnt = ;
while(cnt--) {
printf("%d", t % );
t /= ;
}
printf("\n");
}
return ;
}
D.并查集找到所有跟1能接触的人，做01背包。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
typedef struct P {
int a, b, id;
}P; const int maxn = ;
int n, m, c;
P p[maxn];
int pre[maxn];
int dp[maxn];
int id[maxn]; int find(int x) {
return pre[x] == x ? x : pre[x] = find(pre[x]);
} void unite(int x, int y) {
x = find(x); y = find(y);
if(x != y) pre[x] = y;
} int main() {
// freopen("in", "r", stdin);
int T, u, v;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d",&n,&m,&c);
memset(dp, , sizeof(dp));
for(int i = ; i <= n; i++) pre[i] = i;
for(int i = ; i <= n; i++) {
scanf("%d %d", &p[i].a, &p[i].b);
p[i].id = i;
}
for(int i = ; i < m; i++) {
scanf("%d %d", &u, &v);
unite(u, v);
}
int rt = find();
for(int i = ; i <= n; i++) {
if(rt != find(i)) continue;
for(int j = c; j >= p[i].a; j--) {
dp[j] = max(dp[j], dp[j-p[i].a]+p[i].b);
}
}
printf("%d\n", dp[c]);
}
return ;
}
E.防ak不会…
F.双指针扫，卡住LOVE都出现的最短，然后向后扩展数一共有多少个。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int maxn = ;
char s[maxn];
int vis[];
int n;
int ret;
int l, o, v, e; bool ok() {
return l&&o&&v&&e;
} void update(int i) {
if(s[i]=='L')l++;
if(s[i]=='O')o++;
if(s[i]=='V')v++;
if(s[i]=='E')e++;
} int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
memset(s, , sizeof(s));
scanf("%s", s+);
n = strlen(s+);
ret = ;
int lo, hi;
for(lo = ; lo <= n; lo++) {
// memset(vis, 0, sizeof(vis));
l=o=v=e=;
for(hi = lo; hi <= n; hi++) {
// vis[s[hi]]++;
update(hi);
if(ok()) break;
}
if(hi <= n && ok()) ret = ret + n - hi + ;
}
printf("%d\n", ret);
}
return ;
}
G.BFS，实现得有点SB。。。先特判第一步人能走到哪里。然后更新，在循环里先更新火的状态，这个时候在对内同一层的所有的人的状态面对的地图都是一样的。就可以用一个队列来做了。
#include <bits/stdc++.h>
using namespace std; typedef pair<int, int> pii;
typedef struct P {
int x, y, s;
P() {}
P(int x, int y, int s) : x(x), y(y), s(s) {}
}P;
const int inf = 0x7f7f7f;
const int maxn = ;
const int fdx[] = {-,-,-,,,,,};
const int fdy[] = {-,,,-,,-,,};
const int pdx[] = {-,,,};
const int pdy[] = {,,-,};
int n, m, ret;
int sx, sy, ex, ey, fx, fy;
int fcnt, pcnt;
bool vis[maxn][maxn];
char G[maxn][maxn];
queue<P> q; bool ok(int x, int y) {
return x >= && x < n && y >= && y < m;
} bool nigero(int x, int y) {
return x == ex && y == ey;
} void bfs() {
while(!q.empty()) q.pop();
q.push(P(fx, fy, )); vis[fx][fy] = ; fcnt = ;
int tmp = ;
for(int i = ; i < ; i++) {
int xx = sx + pdx[i];
int yy = sy + pdy[i];
if(nigero(xx, yy)) {
ret = ;
return;
}
if(ok(xx, yy) && G[xx][yy] != '*' && G[xx][yy] != '#' && !vis[xx][yy]) {
vis[xx][yy] = ;
q.push(P(xx, yy, )); tmp++;
}
}
pcnt = tmp; tmp = ;
while(!q.empty()) {
for(int k = ; k < fcnt; k++) {
P f = q.front(); q.pop();
for(int i = ; i < ; i++) {
int xx = f.x + fdx[i];
int yy = f.y + fdy[i];
if(ok(xx, yy) && G[xx][yy] != '*') {
G[xx][yy] = '*';
q.push(P(xx, yy, f.s+)); tmp++;
}
}
}
fcnt = tmp; tmp = ;
for(int k = ; k < pcnt; k++) {
P p = q.front(); q.pop();
if(nigero(p.x, p.y)) {
ret = p.s;
return;
}
if(G[p.x][p.y] == '*') continue;
for(int i = ; i < ; i++) {
int xx = p.x + pdx[i];
int yy = p.y + pdy[i];
if(ok(xx, yy) && G[xx][yy] != '*' && G[xx][yy] != '#' && !vis[xx][yy]) {
vis[xx][yy] = ;
q.push(P(xx, yy, p.s+)); tmp++;
}
}
}
pcnt = tmp; tmp = ;
}
} int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d",&n,&m);
ret = inf;
for(int i = ; i < n; i++) scanf("%s", G[i]);
memset(vis, , sizeof(vis));
for(int i = ; i < n; i++) {
for(int j = ; j < m; j++) {
if(G[i][j] == 'S') {
sx = i; sy = j;
} else if(G[i][j] == 'E') {
ex = i; ey = j;
} else if(G[i][j] == '*') {
fx = i; fy = j;
}
}
}
bfs();
if(ret == inf) puts("T_T");
else printf("%d\n", ret);
}
return ;
}
H.递推发现是个斐波那契，矩阵加速一下就行了。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
const LL mod = ;
const int maxn = ;
LL n; typedef struct Matrix {
LL m[maxn][maxn];
int r;
int c;
Matrix(){
r = c = ;
memset(m, , sizeof(m));
}
} Matrix; Matrix mul(Matrix m1, Matrix m2) {
Matrix ans = Matrix();
ans.r = m1.r;
ans.c = m2.c;
for(int i = ; i <= m1.r; i++) {
for(int j = ; j <= m2.r; j++) {
for(int k = ; k <= m2.c; k++) {
if(m2.m[j][k] == ) continue;
ans.m[i][k] = ((ans.m[i][k] + m1.m[i][j] * m2.m[j][k] % mod) % mod) % mod;
}
}
}
return ans;
} Matrix quickmul(Matrix m, LL n) {
Matrix ans = Matrix();
for(int i = ; i <= m.r; i++) {
ans.m[i][i] = ;
}
ans.r = m.r;
ans.c = m.c;
while(n) {
if(n & ) {
ans = mul(m, ans);
}
m = mul(m, m);
n >>= ;
}
return ans;
} int main() {
// freopen("in", "r", stdin);
int T;
scanf("%d", &T);
while(T--) {
scanf("%lld", &n);
Matrix p, q;
p.r = p.c = ;
p.m[][] = ; p.m[][] = ;
p.m[][] = ; p.m[][] = ;
q.r = ; q.c = ;
if(n <= ) {
printf("%lld\n", n);
continue;
}
q = quickmul(p, n-);
printf("%lld\n", (q.m[][] + q.m[][]) % mod);
}
return ;
}
I.求n次最短路，每次求最短路的时候是以那个点为枢纽。给所有的最短路排序，然后从大到小找两个点，把两条最长的最短路加起来更新答案。
#include <bits/stdc++.h>
using namespace std; typedef pair<int, int> pii;
const int inf = 0x7f7f7f7;
const int maxn = ;
vector<pii> G[maxn];
bool vis[maxn];
queue<int> q;
int d[maxn];
int n, m, ret; void spfa(int s) {
for(int i = ; i <= n; i++) d[i] = inf;
memset(vis, , sizeof(vis));
while(!q.empty()) q.pop();
d[s] = ; q.push(s);
while(!q.empty()) {
int u = q.front(); q.pop();
vis[u] = ;
for(int i = ; i < G[u].size(); i++) {
int& v = G[u][i].first;
int& w = G[u][i].second;
if(d[v] > d[u] + w) {
d[v] = d[u] + w;
if(vis[v]) continue;
vis[v] = ; q.push(v);
}
}
}
sort(d+, d+n+);
int cnt = , x = ;
for(int i = n; i >= ; i--) {
if(cnt >= ) break;
if(d[i] == ) continue;
if(d[i] != inf) {
x += d[i];
cnt++;
}
}
if(cnt == ) ret = max(ret, x);
} int main() {
// freopen("in", "r", stdin);
int u, v, w, T;
scanf("%d", &T);
while(T--) {
ret = -;
scanf("%d%d",&n,&m);
for(int i = ; i <= n; i++) G[i].clear();
for(int i = ; i < m; i++) {
scanf("%d%d%d", &u,&v,&w);
G[u].push_back(pii(v, w));
G[v].push_back(pii(u, w));
}
for(int i = ; i <= n; i++) spfa(i);
printf("%d\n", ret);
}
return ;
}