这道题输入也很阴险！！！
这道题过题姿势最优雅的，不是if else if else if。那样很容易wa的。
如果没有平手选项, 赢得加一分的话, 可以用Landau's Theorem（兰道定理）判定。 稍微修改一下这个定理就能做了。
假设S1,S2……Sn是他们的得分序列，从小到排个序。那么这个序列要是合法。那么当且仅当
- S1+S2+……+Sn = n(n-1）
- S1+S2+……+Si >= i(i-1) ( 1 <= i < n)
其实第二条也可以理解成，第i大的得分，不可能多于2（i-1）,因为你最多把剩下的队伍全部赢一边。
#include <cstdio>
#include <algorithm>
using namespace std;
+ ;
int T, n;
int a[maxn];
void solve()
{
scanf("%d", &n);
; i <= n; i++)
{
scanf("%d", &a[i]);
}
sort(a + , a + n + );
;
; i <= n; i++)
{
sum = sum + a[i];
))
{
printf("F\n");
return ;
}
}
))
printf("F\n");
else
printf("T\n");
}
int main()
{
while(~scanf("%d", &T))
{
while(T--)
{
solve();
}
}
;
}
二分图。每条边理解成一种颜色。则越坏的情况，需要越多的颜色。最坏的情况就是完全二分图。所以就是求完全二分图的边数来作为边界条件。
#include <cstdio>
int main()
{
long long n, m;
while(~scanf("%I64d%I64d", &n, &m))
{
) / ;
* t;
if(ans > m) printf("F\n");
else printf("T\n");
}
;
}
1008 Function
这是。。n²的做法吧。。 竟然AC了，说明。。数据可能只有一万？？？
可能是数据太特殊了吧，st表好像都要跑2000ms。
#include <set>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
const int INF = 0x3f3f3f3f;
+ ;
int ans, a[maxn], net[maxn];
int main()
{
int T, n, m, l, r;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
; i <= n; i++)
{
scanf("%d", &a[i]);
}
mem(net, -);
; i <= n; i++)
{
; j <= n; j++)
{
if(a[j] <= a[i])
{
net[i] = j;
break;
}
}
}
scanf("%d", &m);
while(m--)
{
scanf("%d%d", &l, &r);
ans = a[l];
for(int i = net[l]; i <= r; i = net[i])
{
) break;
}
printf("%d\n", ans);
}
}
;
}
1009 Sparse Graph(补图上求最短路）
标题是稀疏图的意思，它的补图几近为完全图。所以广搜的时候复杂度没有想象的那么高。
这是梦天的做法。。比起刚刚那个好懂多了。。感觉刚刚那个两个set真的还是挺绕的。比较晦涩。
#include <set>
#include <list>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
const int INF = 0x3f3f3f3f;
+ ;
int dis[maxe];
int T, n, m, u, v, S;
void show()
{
; i <= n; i++)
{
if(i == S) continue;
if(dis[i] == INF) printf("-1%c", i == n ? '\n' : ' ');
else printf("%d%c", dis[i], i == n ? '\n' : ' ');
}
}
int main()
{
scanf("%d", &T);
while (T--)
{
mem(dis, -);
list<int> notvis;
set<pair<int, int> > edge;
scanf("%d%d", &n, &m);
; i < m; i++)
{
scanf("%d%d", &u, &v);
edge.insert(make_pair(u, v));
edge.insert(make_pair(v, u));
}
scanf("%d", &S);
; i <= n; i++)
{
if (i != S) notvis.push_back(i);
}
queue<int> que;
que.push(S);
dis[S] = ;
while (!que.empty())
{
int cur = que.front();
que.pop();
for (list<int>::iterator it = notvis.begin(); it != notvis.end();)
{
if (edge.find(make_pair(cur, *it)) == edge.end())
{
que.push(*it);
dis[*it] = dis[cur] + ;
it = notvis.erase(it);
}
else
{
it++;
}
}
}
show();
}
;
1010 Weak Pair（树的dfs序+离散化）
其实就是统计一下a[u]<=K/a[v]，线段树维护。深搜解决。因为数据太大要离散化。
第一种线段树的做法。
#include <set>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
const int INF = 0x3f3f3f3f;
;
], head[maxe * ];
LL k, ans, num[maxe * ], x[maxe * ], sum[(maxe * ) << ];
struct Edge{int to, next;}edge[maxe];
void add_edge(int from,int to)
{
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot++;
}
] + sum[rt << | ];}
void build(int l,int r,int rt)
{
; return ;}
;
build(lson);
build(rson);
pushup(rt);
}
void update(int p,LL add,int l,int r,int rt)
{
if(l == r) {sum[rt] += add; return ;}
;
if(p <= m)
update(p ,add, lson);
else
update(p, add, rson);
pushup(rt);
}
LL query_sum(int ll,int rr,int l,int r,int rt)
{
if(ll <= l && rr >= r) return sum[rt];
LL res = ;
;
if(ll <= m)
res += query_sum(ll, rr, lson);
if(rr > m)
res += query_sum(ll, rr, rson);
return res;
}
void init()
{
ans = ;
tot = ;
mem(head, -);
mem(deep, );
}
void dfs(int u)
{
int o = lower_bound(x, x + numm, k / num[u]) - x;
ans += query_sum(, o, , numm, );
int kk = lower_bound(x, x + numm, num[u]) - x;
update(kk, , , numm, );
for(int i = head[u]; ~i; i = edge[i].next)
{
dfs(edge[i].to);
}
update(kk, -, , numm, );
}
int main()
{
scanf("%d", &T);
while(T--)
{
;
scanf("%d%I64d", &n, &k);
; i <= n; i++)
{
scanf("%I64d", &num[i]);
x[cnt++] = num[i];
x[cnt++] = k / num[i];
}
sort(x, x + cnt);//*****
numm = unique(x, x + cnt) - x;//*****
init();
; i < n - ; i++)
{
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
deep[v]++;
}
build(, numm, );
; i <= n; i++)
{
)
{
dfs(i);
break;
}
}
printf("%I64d\n", ans);
}
;
}
第二种是树状数组的做法：（待补充）