这次好惨，又灰了，都是我自己太不细心导致的。。
A - SwapSort
只要满足交换次数不大于n就可以，n不大，可以乱搞，可是比赛的时候脑抽还是什么，总之不知道写了什么，，，WA了n发以后深刻理解了两变量交换三行式的神奇所在。。竟然有好几组数据被我骗过去了。。
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define LL long long
using namespace std;
const int maxn = 3100;
int num[maxn], id[maxn];
int pp[maxn][2], map[maxn], pos[maxn];
bool cmp(int a, int b)
{
return num[a] < num[b];
}
int main()
{
//freopen("A.in", "r", stdin);
int n, ans = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &num[i]);
for(int i = 0; i < n; i++)
id[i] = i;
sort(id, id + n, cmp);
for(int i = 0; i < n; i++)
map[id[i]] = i;
for(int i = 0; i < n; i++)
{
int j;
// for(j = 0; j < n; j++)
// cout << map[j] << ' ';
// cout << endl;
for(j = 0; j < n; j++)
{
if(map[j] == i)
break;
}
if(i != j && j < n)
{
pp[ans][0] = i;
pp[ans][1] = j;
ans++;
int tmp = map[i];
map[i] = map[j];
map[j] = tmp;
}
}
printf("%d\n", ans);
for(int i = 0; i < ans; i++)
printf("%d %d\n", pp[i][0], pp[i][1]);
return 0;
}
B - BerSU Ball
二分匹配的变形，模板题【唯一没有fst的题，，论模板的重要性】
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#define LL long long
using namespace std;
const int maxn = 110;
int bb[maxn], gg[maxn];
vector<int> edge[maxn];
bool vis[maxn];
int n, m;
int pp[maxn];
bool find_path(int x)
{
for(int i = 0; i < n; i++)
{
if(!vis[i])
{
bool flag = true;
for(int k = 0; k < edge[i].size(); k++)
{
if(edge[i][k] == x)
{
flag = false;
break;
}
}
if(flag)
continue;
vis[i] = true;
if(pp[i] == -1 || find_path(pp[i]))
{
pp[i] = x;
// cout << "id: " << i << ' ' << x << endl;
// cout << "sk: " << bb[i] << ' ' << gg[x] << endl;
return true;
}
}
}
return false;
}
int main()
{
//freopen("B.in", "r", stdin);
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &bb[i]);
scanf("%d", &m);
for(int i = 0; i < m; i++)
scanf("%d", &gg[i]);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if((bb[i] - gg[j]) * (bb[i] - gg[j]) <= 1)
{
edge[i].push_back(j);
}
}
}
int ans = 0;
memset(pp, -1, sizeof(pp));
for(int i = 0; i < m; i++)
{
memset(vis, false, sizeof(vis));
if(find_path(i))
ans++;
}
printf("%d\n", ans);
return 0;
}
C - Given Length and Sum of Digits...
少了个剪枝，结果tle到死，，，好不容易pp了， 结果fst。。。加个判断：剩下的数位和除以总数位是否大于9，秒过。
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int m, s;
int ans;
char cnt[110];
void dfs(int k, int sum)
{
if(ans != -1)
return ;
if(k == m)
{
if(ans == -1 && sum == s)
{
ans = 0;
printf("%s ", cnt);
}
return ;
}
for(int i = 0; i < 10; i++)
{
if(k == 0 && i == 0)
continue;
if((s - sum) / (m - k) > 9 || (s - sum) / (m - k) == 9 && (s - sum) % (m - k) != 0)
continue;
cnt[k] = '0' + i;
dfs(k + 1, sum + i);
}
}
void min_num()
{
ans = -1;
dfs(0, 0);
}
int max_num()
{
int x = s / 9;
int y = s % 9;
if(x > m || x == m && y != 0)
return -1;
else
{
for(int i = 0; i < m; i++)
{
if(i < x)
cnt[i] = '0' + 9;
else if(i == x)
cnt[i] = '0' + y;
else
cnt[i] = '0';
}
cnt[m] = '\0';
printf("%s\n", cnt);
}
}
int main()
{
//freopen("C.in", "r", stdin);
scanf("%d%d", &m, &s);
if(m == 1 && s == 0)
printf("0 0\n");
else if(m == 0 || s == 0)
printf("-1 -1\n");
else if((s / m) > 9 || s / m == 9 && s % m != 0)
printf("-1 -1\n");
else if((s / m) == 9 && (s % m) == 0)
{
memset(cnt, '9', sizeof(cnt[0]) * m);
printf("%s %s\n", cnt, cnt);
}
else
{
min_num();
max_num();
}
return 0;
}
D - Unbearable Controversy of Being（暴力）
给一张图，数图片里的菱形有多少个。
感觉D题水得不符合题号。。两个for循环暴力，找出两个点间有多少条长度为2的路径【有向】，然后用组合数算出两两组合有多少，最后求总和即可。
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 3010;
const int maxm = 30010;
vector<int> mm[maxn];
bool ee[maxn][maxn];
int n, m;
int a, b;
int make_Road(int x, int y)
{
int ret = 0;
for(int i = 0; i < mm[x].size(); i++)
{
//cout << x << ' ' << mm[x][i] << ' ' << y << endl;
if(ee[x][mm[x][i]] && ee[mm[x][i]][y])
ret++;
}
//cout << ret << endl;
return ret * (ret - 1) / 2;
}
int main()
{
//freopen("D.in", "r", stdin);
scanf("%d%d", &n, &m);
if(n == 0 || m == 0)
{
printf("0\n");
return 0;
}
memset(ee, false, sizeof(ee));
for(int i = 0; i < n; i++)
mm[i].clear();
for(int i = 0; i < m; i++)
{
scanf("%d%d", &a, &b);
ee[a][b] = true;
mm[a].push_back(b);
}
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j)
ans += make_Road(i, j);
printf("%d\n", ans);
return 0;
}
E - Hiking （分数规划）
为了E题去学习了一下分数规划。
E题是最简单的01分数规划，首先写出表达式f(r)=∑sqrt(|xi-xj-l|) - r*∑bi，要求所求的r是最小的，则在最优方案下，不是最优的r的解，会使得f(r)为负。
dp[i]表示走到第i块石头时，最小的f(r)。
当dp[n]不为0时，说明r不为最优解。令r为这个方案下的r'，再重新求解，逐渐靠近最优解。
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
using namespace std;
#define INF 1e100
#define EPS 1e-8
const int maxn=1010;
double x[maxn],b[maxn];
double dp[maxn],dx[maxn],dy[maxn];
int n,l,que[maxn],pre[maxn];
int sig(double x)
{
return (x>EPS)-(x<-EPS);
}
int main()
{
//freopen("E.in","r",stdin);
scanf("%d%d",&n,&l);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&b[i]);
x[0]=b[0]=0.0;
double r=0.0;
int k = 10;
while(k--)
{
// cout<<r<<endl;
for(int i=1;i<=n;i++)
{
dp[i]=INF;
dx[i]=dy[i]=0.0;
}
dp[0]=dx[0]=dy[0]=0.0;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
{
double df=sqrt(fabs(x[i]-x[j]-l))-r*b[i];
if(dp[j]+df<dp[i])
{
// cout<<dp[i]<<' '<<dp[j]<<' '<<df<<endl;
dp[i]=dp[j]+df;
pre[i]=j;
dy[i]=dy[j]+sqrt(fabs(x[i]-x[j]-l));
dx[i]=dx[j]+b[i];
}
}
if(sig(dp[n]) == 0)
break;
r=dy[n]/dx[n];
}
int tot=0;
while(n){
que[tot++]=n;
n=pre[n];
}
for(int i=tot-1;i>0;i--)
printf("%d ",que[i]);
printf("%d\n",que[0]);
return 0;
}