#B Geometry Problem
计算几何，给定两条线段，求一个圆，使得此圆与两线段均有且仅有一个严格相交的交点
做法之一为：在两个圆上找最近的一对端点，以连线为直径做圆，然后将半径略微扩大即可
AC-Code（关键部分）
double td = 1e5;
if (td > dist(p11, p21))
{
td = dist(p11, p21);
ans = Circle(p11, p21);
}
if (td > dist(p11, p22))
{
td = dist(p11, p22);
ans = Circle(p11, p22);
}
if (td > dist(p12, p21))
{
td = dist(p12, p21);
ans = Circle(p12, p21);
}
if (td > dist(p12, p22))
{
td = dist(p12, p22);
ans = Circle(p12, p22);
}
ans.r += 0.002;
#C Important Roads
给定一个图（可能有自环和重边），如果去掉某边可使得最短路变长（或不存在）则称此边为“Important Road”求Important Roads组成的集合
求最短路，对最短路建图，之后跑Tarjan求桥即可
AC-Code (略去了Dijkstra和Tarjan)
const int maxn = 20000 + 5;
long long d[maxn] , d2[maxn];
int vis[maxn];
bool bridge[100000 + 5];
typedef pair<int , int> pii;
map<pii , int> mm;
map<pii , int> md;
vector<int> e[maxn];
int n , m;
struct Pri{
int v;
long long c;
Pri(){}
Pri(int _v , long long _c):v(_v) , c(_c){}
bool operator <(Pri o)const{
return c > o.c;
}
};
typedef vector<Pri>::iterator iter;
vector<Pri>p[maxn];
void dijkstra(int scr);
int dfn[maxn] , low[maxn];
void cbridge(int cur , int father , int dep);
int main()
{
#ifdef ONLINE_JUDGE
freopen("important.in" , "r" , stdin);
freopen("important.out" , "w" , stdout);
#endif
scanf("%d%d" , &n , &m);
int u , v , w;
for (int i = 1 ; i <= m ; i++)
{
scanf("%d%d%d" , &u , &v , &w);
p[u].push_back(Pri(v , w));
p[v].push_back(Pri(u , w));
if (mm[pii(u , v)] == 0 || md[pii(u , v)] > w)
{
md[pii(u , v)] = md[pii(v , u)] = w;
mm[pii(u , v)] = mm[pii(v , u)] = i;
}else if (md[pii(u , v)] == w)
{
mm[pii(u , v)] = mm[pii(v , u)] = m + 1;
}
}
dijkstra(1);
memset(vis , 0 , sizeof(vis));
memcpy(d2 , d , sizeof(d));
dijkstra(n);
for (int i = 1 ; i <= n ; i++)
{
for (int j = 0 ; j < p[i].size() ; j++)
{
v = p[i][j].v;
w = p[i][j].c;
if (d2[i] + d[v] + w == d2[n])
{
e[i].push_back(v);
e[v].push_back(i);
}
}
}
memset(vis , 0 , sizeof(vis));
cbridge(1 , -1 , 0);
int cnt = 0;
for (int i = 1 ; i <= m ; i++)
if (bridge[i])
cnt++;
printf("%d\n" , cnt);
for (int i = 1 ; i <= m ; i++)
if (bridge[i])
printf("%d%c" , i , (--cnt)?' ':'\n');
return 0;
}
#F Spam Filter
依题意模拟即可
其实不需要用Double，式子是可以简化的
#include <bits/stdc++.h>
using namespace std;
const int maxwords = 1000 * 100 * 3 + 5;
const int mod = 1e15 + 7;
double ps[maxwords] , pg[maxwords];
int cspam , cgood , cto , t;
map<unsigned long long , int> wdid;
int wcnt;
string buf;
void process_setense(double arr[])
{
unsigned long long wd = 0;
int len = 0;
while (len == 0)
{
getline(cin , buf);
len = buf.size();
}
buf = buf + "!!!";
len = buf.size();
set<int> word;
for (int i = 0 ; i < len ; i++)
{
if ('a' <= buf[i] && buf[i] <= 'z')
wd = (wd * 29 + buf[i] - 'a' + 1) % mod;
else if ('A' <= buf[i] && buf[i] <= 'Z')
wd = (wd * 29 + buf[i] - 'A' + 1) % mod;
else
{
if (wd == 0)
continue;
int wid = wdid[wd];
if (wid == 0)
wdid[wd] = wid = (++wcnt);
word.insert(wid);
wd = 0;
}
}
for (set<int>::iterator it = word.begin() ; it != word.end() ; it++)
arr[*it] = arr[*it] + 1;
}
bool process_setense()
{
unsigned long long wd = 0;
int badcnt = 0;
int totcnt = 0;
int len = 0;
while (len == 0)
{
getline(cin , buf);
len = buf.size();
}
buf = buf + "!!!";
len = buf.size();
set<int> word;
for (int i = 0 ; i < len ; i++)
{
if ('a' <= buf[i] && buf[i] <= 'z')
{
wd = (wd * 29 + buf[i] - 'a' + 1) % mod;
}
else if ('A' <= buf[i] && buf[i] <= 'Z')
{
wd = (wd * 29 + buf[i] - 'A' + 1) % mod;
}
else
{
if (wd == 0)
continue;
int wid = wdid[wd];
if (wid == 0)
wdid[wd] = wid = (++wcnt);
wd = 0;
if (*word.lower_bound(wid) != wid)
totcnt++;
if (wid == 0)
continue;
word.insert(wid);
wd = 0;
}
}
for (set<int>::iterator it = word.begin() ; it != word.end() ; it++)
if (ps[*it] + pg[*it] > 0.1 && ps[*it] > pg[*it] - 0.1)
badcnt++;
if (totcnt == 0)
return false;
return ((badcnt * 100 / totcnt) >= t);
}
int main()
{
#ifdef ONLINE_JUDGE
freopen("spam.in" , "r" ,stdin);
freopen("spam.out" , "w" , stdout);
#endif
ios::sync_with_stdio(0);
getline(cin , buf);
sscanf(buf.c_str() , "%d%d%d%d" , &cspam , &cgood , &cto , &t);
for (int i = 0 ; i < cspam ; i++)
process_setense(ps);
for (int i = 0 ; i < cgood ; i++)
process_setense(pg);
for (int i = 0 ; i < cto ; i++)
printf("%s\n" , process_setense() ? "spam" : "good");
return 0;
}
#I TV Show
枚举使用保险的位置，暴力即可
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 55;
double prob[maxn];
int c;
int n;
double dfs(int lev, int use, double curr)
{
if (lev == n)
return curr;
if (lev == use)
return dfs(lev + 1, use, (curr - c) + prob[lev] * (curr - c));
return max(curr, dfs(lev + 1, use, curr * 2) * prob[lev]);
}
int main()
{
#ifdef ONLINE_JUDGE
freopen("tvshow.in", "r", stdin);
freopen("tvshow.out", "w", stdout);
#endif
scanf("%d%d", &n, &c);
for (int i = 0; i < n; i++)
{
scanf("%lf", &prob[i]);
prob[i] /= 100;
}
double ans = 0;
for (int i = 0; i <= n; i++)
ans = max(ans, dfs(0, i, 100));
printf("%.12f\n", ans);
return 0;
}