1.LA 5694 Adding New Machine
关键词：数据结构，线段树，扫描线(FIFO)
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 1ll << ;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e6 + ;
const double double_inf = 1e30;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y)) inline int readint(){
bool neg = ; char ch, t[];
int k = ;
while((ch = getchar()) == ' ' || ch == '\n' || ch == ) ;
neg = ch == '-';
ch == '-' ? neg = : t[k++] = ch;
while((ch = getchar()) >= '' && ch <= '') t[k++] = ch;
//__ch = ch;
int x = , y = ;
while(k) x += (t[--k] - '') * y, y *= ;
return neg ? -x : x;
} inline int readstr(char *s){
char ch;
int len = ;
while((ch = getchar()) == ' ' || ch == '\n' || ch == ) ;
if(ch == EOF) return ;
*(s++) = ch, ++len;
while((ch = getchar()) != ' ' && ch != '\n' && ch != EOF) *(s++) = ch, ++len;
*s = '\0';
return len;
}
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
};
int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
int n = 1e2 + ;
//freopen("in.txt", "w", stdout);
printf("%d\n", n);
srand(time());
FOR(i, , n){
int x = Rand(1e5, ), y = Rand(x, ) + (x ? Rand(, ) : ), z = Rand(y, ) + (y ? Rand(, ) : );
printf("%d %d %d\n", x, y, z);
//solve(x, y, z);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
const int maxn = 5e4 + ;
const int maxm = maxn << ;
struct Seg{
int l, r, lg, rg;
int cnt, length, lazy;
}seg[maxm << ];
pair<pii, pii> a[maxn];
int n, m, w, h;
int buf[maxm], k;
map<int, int> mapx, mapy;
vector<pii> info[maxm];
int anx[maxm], any[maxm]; void build(int u, int l, int r, int o){
seg[u].l = l, seg[u].r = r;
seg[u].lazy = ;
seg[u].length = o ? anx[r] - anx[l] : any[r] - any[l];
seg[u].lg = seg[u].rg = seg[u].length;
seg[u].cnt = max(, seg[u].length - m + );
if(r - l < ) return;
int mid = (l + r) >> ;
build(lson, l, mid, o), build(rson, mid, r, o);
} void push_down(int u){
seg[lson].lazy += seg[u].lazy, seg[rson].lazy += seg[u].lazy;
if(seg[u].lazy < ){
seg[lson].cnt = max(, seg[lson].length - m + );
seg[rson].cnt = max(, seg[rson].length - m + );
seg[lson].lg = seg[lson].rg = seg[lson].length;
seg[rson].lg = seg[rson].rg = seg[rson].length;
}else if(seg[u].lazy > ){
seg[lson].cnt = seg[rson].cnt = ;
seg[lson].lg = seg[lson].rg = ;
seg[rson].lg = seg[rson].rg = ;
}
} void push_up(int u){
int tem = seg[lson].cnt + seg[rson].cnt;
tem -= max(, seg[lson].rg - m + );
tem -= max(, seg[rson].lg - m + );
tem += max(, seg[lson].rg + seg[rson].lg - m + );
seg[u].cnt = tem;
seg[u].lg = seg[lson].lg + (seg[lson].lg == seg[lson].length ? seg[rson].lg : );
seg[u].rg = seg[rson].rg + (seg[rson].rg == seg[rson].length ? seg[lson].rg : );
} void update(int u, int l, int r, int o){
if(seg[u].l == l && seg[u].r == r){
seg[u].lazy += o;
if(o < ){
seg[u].cnt = max(, seg[u].length - m + );
seg[u].lg = seg[u].rg = seg[u].length;
}else seg[u].cnt = seg[u].lg = seg[u].rg = ;
return;
}
push_down(u);
int mid = (seg[u].l + seg[u].r) >> ;
if(r <= mid) update(lson, l, r, o);
else if(l >= mid) update(rson, l, r, o);
else update(lson, l, mid, o), update(rson, mid, r, o);
push_up(u);
} //-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(~scanf("%d", &w)){
h = readint(), n = readint(), m = readint();
FOR(i, , n - ){
int x1 = readint(), y1 = readint(), x2 = readint(), y2 = readint();
a[i] = mp(mp(x1, y1), mp(x2, y2));
}
k = ;
FOR(i, , n - ) buf[k++] = a[i].st.nd, buf[k++] = a[i].nd.nd + ;
buf[k++] = , buf[k++] = h + ;
sort(buf, buf + k);
k = unique(buf, buf + k) - buf;
mapy.clear();
FOR(i, , k - ) mapy[buf[i]] = i + , any[i + ] = buf[i];
build(, , k, );
k = ;
FOR(i, , n - ) buf[k++] = a[i].st.st, buf[k++] = a[i].nd.st + ;
buf[k++] = , buf[k++] = w + ;
sort(buf, buf + k);
k = unique(buf, buf + k) - buf;
mapx.clear();
FOR(i, , k - ) mapx[buf[i]] = i + , anx[i + ] = buf[i];
FOR(i, , k) info[i].clear();
FOR(i, , n - ) info[mapx[a[i].st.st]].pb(mp(, i)), info[mapx[a[i].nd.st + ]].pb(mp(-, i));
ll ans = ;
FOR(i, , k - ){
int sz = info[i].size();
sort(info[i].begin(), info[i].end());
FOR(j, , sz - ){
int lhs = mapy[a[info[i][j].nd].st.nd], rhs = mapy[a[info[i][j].nd].nd.nd + ];
update(, lhs, rhs, info[i][j].st);
}
ans += (ll)(anx[i + ] - anx[i]) * seg[].cnt;
}
build(, , mapx[w + ], );
k = mapy[h + ];
FOR(i, , k) info[i].clear();
FOR(i, , n - ) info[mapy[a[i].st.nd]].pb(mp(, i)), info[mapy[a[i].nd.nd + ]].pb(mp(-, i));
FOR(i, , k - ){
int sz = info[i].size();
sort(info[i].begin(), info[i].end());
FOR(j, , sz - ){
int lhs = mapx[a[info[i][j].nd].st.st], rhs = mapx[a[info[i][j].nd].nd.st + ];
update(, lhs, rhs, info[i][j].st);
}
ans += (ll)(any[i + ] - any[i]) * seg[].cnt;
}
if(m == ) ans >>= 1ll;
printf("%lld\n", ans);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code:
2.LA 5698 Draw A Mess
关键词：数据结构，线段树，平时时间空间开销
(此题另有并查集解法)
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 1ll << ;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e6 + ;
const double double_inf = 1e30;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y)) inline int readint(){
bool neg = ; char ch, t[];
int k = ;
while((ch = getchar()) == ' ' || ch == '\n' || ch == ) ;
neg = ch == '-';
ch == '-' ? neg = : t[k++] = ch;
while((ch = getchar()) >= '' && ch <= '') t[k++] = ch;
//__ch = ch;
int x = , y = ;
while(k) x += (t[--k] - '') * y, y *= ;
return neg ? -x : x;
} inline int readstr(char *s){
char ch;
int len = ;
while((ch = getchar()) == ' ' || ch == '\n' || ch == ) ;
if(ch == EOF) return ;
*(s++) = ch, ++len;
while((ch = getchar()) != ' ' && ch != '\n' && ch != EOF) *(s++) = ch, ++len;
*s = '\0';
return len;
}
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
};
int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
int n = 1e2 + ;
//freopen("in.txt", "w", stdout);
printf("%d\n", n);
srand(time());
FOR(i, , n){
int x = Rand(1e5, ), y = Rand(x, ) + (x ? Rand(, ) : ), z = Rand(y, ) + (y ? Rand(, ) : );
printf("%d %d %d\n", x, y, z);
//solve(x, y, z);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
struct Seg{
int l, r;
int cnt[];
int lazy;
}seg[ << ];
int n, m, q;
void build(int u, int l, int r){
seg[u].lazy = ;
seg[u].l = l, seg[u].r = r;
clr(seg[u].cnt, );
if(r - l < ) return;
int mid = (r + l) >> ;
build(lson, l, mid), build(rson, mid, r);
} void push_up(int u){
FOR(i, , ) seg[u].cnt[i] = seg[lson].cnt[i] + seg[rson].cnt[i];
} void push_down(int u){
if(seg[u].lazy == ) return;
clr(seg[lson].cnt, ), clr(seg[rson].cnt, );
seg[lson].cnt[seg[u].lazy] = seg[lson].r - seg[lson].l;
seg[rson].cnt[seg[u].lazy] = seg[rson].r - seg[rson].l;
seg[lson].lazy = seg[rson].lazy = seg[u].lazy;
seg[u].lazy = ;
} void update(int u, int l, int r, int c){
if(seg[u].l == l && seg[u].r == r){
seg[u].lazy = c;
clr(seg[u].cnt, );
seg[u].cnt[c] = seg[u].r - seg[u].l;
return;
}
push_down(u);
int mid = (seg[u].l + seg[u].r) >> ;
if(r <= mid) update(lson, l, r, c);
else if(l >= mid) update(rson, l, r, c);
else update(lson, l, mid, c), update(rson, mid, r, c);
push_up(u);
}
int op[][];
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(~scanf("%d", &n)){
m = readint(), q = readint();
char cmd[];
FOR(i, , q){
readstr(cmd);
if(cmd[] == 'D') op[i][] = ;
else if(cmd[] == 'T') op[i][] = ;
else if(cmd[] == 'R') op[i][] = ;
else if(cmd[] == 'C') op[i][] = ;
FOR(j, , ) op[i][j] = readint();
if(cmd[] == 'R') op[i][] = readint();
}
int ans[];
clr(ans, );
FOR(i, , n - ){
build(, , m);
FOR(j, , q){
int x = op[j][], y = op[j][], z = op[j][], u = op[j][], v = op[j][];
if(op[j][] == ){
int low = max(, x - z), high = min(n - , x + z);
if(i < low || i > high) continue;
int len = z - abs(i - x);
int l = max(, y - len), r = min(m - , y + len);
update(, l, r + , u);
}else if(op[j][] == ){
int low = x, high = min(n - , x + (z - ) / );
if(i < low || i > high) continue;
int len = (z - ) / - (i - x);
int l = max(, y - len), r = min(m - , y + len);
update(, l, r + , u);
}else if(op[j][] == ){
int low = x, high = min(n - , x + z - );
if(i < low || i > high) continue;
int l = y, r = min(m - , y + u - );
update(, l, r + , v);
}else{
int low = max(, x - z), high = min(n - , x + z);
if(i < low || i > high) continue;
ll len2 = (ll)z * z - (ll)(abs(i - x)) * abs(i - x);
ll len = (ll)sqrt(len2);
ll l = max(, y - len), r = min(m - , y + len);
update(, l, r + , u);
}
}
FOR(i, , ) ans[i] += seg[].cnt[i];
}
printf("%d", ans[]);
FOR(i, , ) printf(" %d", ans[i]);
printf("\n");
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code:
3.LA 4013 A Sequence of Numbers
关键词：数据结构，线段树，记忆化处理，问题转换
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 1ll << ;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e6 + ;
const double double_inf = 1e30;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y)) inline int readint(){
bool neg = ; char ch, t[];
int k = ;
while((ch = getchar()) == ' ' || ch == '\n' || ch == ) ;
neg = ch == '-';
ch == '-' ? neg = : t[k++] = ch;
while((ch = getchar()) >= '' && ch <= '') t[k++] = ch;
//__ch = ch;
int x = , y = ;
while(k) x += (t[--k] - '') * y, y *= ;
return neg ? -x : x;
} inline int readstr(char *s){
char ch;
int len = ;
while((ch = getchar()) == ' ' || ch == '\n' || ch == ) ;
if(ch == EOF) return ;
*(s++) = ch, ++len;
while((ch = getchar()) != ' ' && ch != '\n' && ch != EOF) *(s++) = ch, ++len;
*s = '\0';
return len;
}
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
};
int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
int times = ;
freopen("in.txt", "w", stdout);
while(times--){
int n = 1e5;
printf("%d\n", n);
srand(time());
FOR(i, , n){
int x = Rand( << , );
printf("%d\n", x);
//solve(x, y, z);
}
int m = 1e5;
FOR(i, , m){
int op = Rand(, );
if(op){
printf("Q %d\n", Rand(, ));
}else printf("C %d\n", Rand( << , ));
}
puts("E\n");
}
puts("-1");
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//------------------------------------------------------------------------
int a[ << ];
const int maxn = 2e5 + ;
struct Seg{
int l, r;
int cnt;
}seg[( << ) << ];
int bg;//[bg, bg + (1 << 16)) void push_up(int u){
seg[u].cnt = seg[lson].cnt + seg[rson].cnt;
} void build(int u, int l, int r){
seg[u].r = r, seg[u].l = l;
seg[u].cnt = ;
if(r - l < ){
if(l >= bg && l < bg + ( << )) seg[u].cnt += a[l - bg];
return;
}
int mid = (l + r) >> ;
build(lson, l, mid), build(rson, mid, r);
push_up(u);
} void insert(int u, int l, int r, int v){
if(seg[u].r == r && seg[u].l == l){
seg[u].cnt = v;
return;
}
int mid = (seg[u].l + seg[u].r) >> ;
if(r <= mid) insert(lson, l, r, v);
else if(l >= mid) insert(rson, l, r, v);
push_up(u);
} int query(int u, int l, int r){
if(seg[u].l == l && r == seg[u].r) return seg[u].cnt;
int mid = (seg[u].l + seg[u].r) >> ;
if(r <= mid) return query(lson, l, r);
else if(l >= mid) return query(rson, l, r);
else return query(lson, l, mid) + query(rson, mid, r);
} int _query(int l, int r){
l = (l + ( << )) % ( << ), r = (r + ( << )) % ( << );
if(l <= r) return query(, l, r + );
else return query(, l, << ) + query(, , r + );
} int ans[][ << ];
int n;
int getAns(int i, int times){
if(ans[i][times] != -) return ans[i][times];
int lim = ( << (i + )) - ;
int tans = ;
int tem = << i;
while(tem <= ( << ) - ){
tans += _query(tem - times, tem + ( << i) - times - );
tem += ( << (i + ));
}
return ans[i][times] = tans;
} //-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int kase = ;
while(~scanf("%d", &n) && ~n){
clr(a, );
FOR(i, , n - ) ++a[readint()];
build(, , << );
int lim = ( << ) - ;
clr(ans, -);
char ch;
ll _ans = ;
int shift = ;
while(~scanf(" %c", &ch) && ch != 'E'){
int tem = readint();
tem %= << ;
if(ch == 'C') shift = (shift + tem) % ( << );
else _ans += getAns(tem, shift % ( << (tem + )));
}
printf("Case %d: %lld\n", ++kase, _ans);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code:
4.Uva 11019 Matrix Matcher
关键词：数据结构，字符串，AC自动机
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 1ll << ;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e6 + ;
const double double_inf = 1e30;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y)) inline int readint(){
int x;
scanf("%d", &x);
return x;
} inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
} class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int n = Rand(, ), m = Rand(, );
printf("%d %d\n", n, m);
FOR(i, , n){
FOR(j, , m) printf("%c", Rand(, ) + 'a');
putchar('\n');
}
n = Rand(min(, n), ), m = Rand(min(, m), );
printf("%d %d\n", n, m);
FOR(i, , n){
FOR(j, , m) printf("%c", Rand(, ) + 'a');
putchar('\n');
}
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
const int maxn = 1e3 + ;
char mt_t[maxn][maxn];
char mt_p[][];
int mt_t_n[maxn][maxn];
int mt_p_n[];
const int sigma_size = ;
int n, m, X, Y;
int ch[ * ][sigma_size];
int idx(char c) { return c - 'a'; }
int id[ * ];
struct Trie{
int sz, cnt;
void init() { clr(ch[], ); cnt = sz = ; clr(id, ); }
int insert(char *src){
int u = ;
while(*src){
int v = ch[u][idx(*src)];
if(!v) { v = ch[u][idx(*src)] = ++sz; clr(ch[sz], ); }
u = v;
src++;
}
if(!id[u]) id[u] = ++cnt;
return id[u];
}
}trie;
int fail[ * ];
queue<int> q;
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("_in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int kases = readint();
while(kases--){
n = readint(), m = readint();
trie.init();
FOR(i, , n - ) scanf("%s", mt_t[i]);
X = readint(), Y = readint();
FOR(i, , X - ) scanf("%s", mt_p[i]);
FOR(i, , X - ) mt_p_n[i] = trie.insert(mt_p[i]);
while(!q.empty()) q.pop();
fail[] = ;
FOR(i, , sigma_size - ) if(ch[][i]) q.push(ch[][i]), fail[ch[][i]] = ;
while(!q.empty()){
int u = q.front(); q.pop();
FOR(i, , sigma_size - ){
int v = ch[u][i];
if(!v) continue;
int j = fail[u];
while(j && !ch[j][i]) j = fail[j];
fail[v] = ch[j][i];
q.push(v);
}
}
FOR(i, , n - ){
int pointer = ;
FOR(j, , m - ){
int c = idx(mt_t[i][j]);
if(ch[pointer][c]) pointer = ch[pointer][c];
else{
pointer = fail[pointer];
while(pointer && !ch[pointer][c]) pointer = fail[pointer];
pointer = ch[pointer][c];
}
mt_t_n[i][j] = j >= Y - ? id[pointer] : ;
}
}
fail[] = -;
FOR(i, , X - ){
int j = fail[i - ];
while(j != - && mt_p_n[j + ] != mt_p_n[i]) j = fail[j];
fail[i] = mt_p_n[j + ] == mt_p_n[i] ? j + : -;
}
int ans = ;
FOR(i, , m - ){
int pointer = -;
FOR(j, , n - ){
if(pointer < X - && mt_p_n[pointer + ] == mt_t_n[j][i]) ++pointer;
else if(pointer != -){
pointer = fail[pointer];
while(pointer != - && mt_p_n[pointer + ] != mt_t_n[j][i]) pointer = fail[pointer];
pointer = mt_p_n[pointer + ] == mt_t_n[j][i] ? + pointer : -;
}
ans += pointer == X - ;
}
}
printf("%d\n", ans);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code:
5.LA 5913 Dictionary Size
关键词：树结构，字符串，trie，前缀后缀
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 1ll << ;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e6 + ;
const double double_inf = 1e30;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y)) inline int readint(){
int x;
scanf("%d", &x);
return x;
} inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
} class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int n = Rand(, ), m = Rand(, );
printf("%d %d\n", n, m);
FOR(i, , n){
FOR(j, , m) printf("%c", Rand(, ) + 'a');
putchar('\n');
}
n = Rand(min(, n), ), m = Rand(min(, m), );
printf("%d %d\n", n, m);
FOR(i, , n){
FOR(j, , m) printf("%c", Rand(, ) + 'a');
putchar('\n');
}
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
const int maxn = 1e4 + ;
const int sigma_size = ;
int cnt[], valid[], cnt_all;
struct Trie{
int ch[maxn * ][sigma_size];
int w[maxn * ];
int sz;
void init() { clr(ch[], ); sz = ; clr(w, ); }
int idx(int c) { return c - 'a'; }
void insert(char *s, int o){
int u = ;
while(*s){
int v = ch[u][idx(*s)];
if(!v) { v = ch[u][idx(*s)] = ++sz; clr(ch[sz], ); }
u = v;
s += o;
}
w[u] = ;
}
void dfs_2(int u){
++cnt_all;
FOR(i, , sigma_size - ) if(!ch[u][i]) ++cnt[i];
FOR(i, , sigma_size - ) valid[i] = ch[][i] > ;
FOR(i, , sigma_size - ) if(ch[u][i]) dfs_2(ch[u][i]);
}
void cal_2(){
clr(cnt, );
cnt_all = ;
FOR(i, , sigma_size - ) if(ch[][i]) dfs_2(ch[][i]);
}
ll dfs_1(int fa, int u, int o){
ll tem = !fa ? cnt_all : cnt[o];
if(w[u] && !(fa && valid[o])) ++tem;
FOR(i, , sigma_size - ) if(ch[u][i]) tem += dfs_1(u, ch[u][i], i);
return tem;
}
ll cal_1(){
ll ans = ;
FOR(i, , sigma_size - ) if(ch[][i]) ans += dfs_1(, ch[][i], i);
return ans;
}
}trie1, trie2;
char mt[maxn][];
int len[maxn];
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int n;
while(~scanf("%d", &n)){
FOR(i, , n - ) len[i] = readstr(mt[i] + ), mt[i][] = '\0';
trie1.init(), trie2.init();
FOR(i, , n - ) trie1.insert(mt[i] + , ), trie2.insert(mt[i] + len[i], -);
trie2.cal_2();
ll ans = trie1.cal_1();
printf("%lld\n", ans);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code:
6.LA 4108 Skyline
关键词：线段树，注意数据范围
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 1ll << ;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e6 + ;
const double double_inf = 1e30;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y)) inline int readint(){
int x;
scanf("%d", &x);
return x;
} inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
} class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int n = Rand(, ), m = Rand(, );
printf("%d %d\n", n, m);
FOR(i, , n){
FOR(j, , m) printf("%c", Rand(, ) + 'a');
putchar('\n');
}
n = Rand(min(, n), ), m = Rand(min(, m), );
printf("%d %d\n", n, m);
FOR(i, , n){
FOR(j, , m) printf("%c", Rand(, ) + 'a');
putchar('\n');
}
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
const int maxn = 1e5 + ;
struct Seg{
int l, r, maxi, mini;
int lazy;
}seg[maxn << ];
void build(int u, int l, int r){
seg[u].l = l, seg[u].r = r;
seg[u].maxi = seg[u].mini = seg[u].lazy = ;
if(r - l < ) return;
int mid = (l + r) >> ;
build(lson, l, mid), build(rson, mid, r);
} void push_up(int u){
seg[u].mini = min(seg[lson].mini, seg[rson].mini);
seg[u].maxi = max(seg[lson].maxi, seg[rson].maxi);
} void push_down(int u){
if(!seg[u].lazy) return;
seg[lson].maxi = seg[lson].mini = seg[u].lazy;
seg[rson].maxi = seg[rson].mini = seg[u].lazy;
seg[lson].lazy = seg[rson].lazy = seg[u].lazy;
seg[u].lazy = ;
} int update(int u, int l, int r, int value){
if(seg[u].l == l && seg[u].r == r){
if(seg[u].mini > value) return ;
if(seg[u].maxi <= value){
seg[u].maxi = seg[u].mini = value;
seg[u].lazy = value;
return seg[u].r - seg[u].l;
}
int mid = (l + r) >> ;
return update(lson, l, mid, value) + update(rson, mid, r, value);
}
push_down(u);
int mid = (seg[u].l + seg[u].r) >> ;
int tem = ;
if(r <= mid) tem = update(lson, l, r, value);
else if(l >= mid) tem = update(rson, l, r, value);
else tem = update(lson, l, mid, value) + update(rson, mid, r, value);
push_up(u);
return tem;
} int n;
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int T = readint();
while(T--){
n = readint();
build(, , maxn - );
int ans = ;
FOR(i, , n){
int x = readint(), y = readint(), z = readint();
ans += update(, x, y, z);
}
printf("%d\n", ans);
}
T = readint();
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code:
7.LA 4119 Always an integer
关键词：递推，模拟，字符处理
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 1ll << ;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e9 + ;
const double double_inf = 1e30;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x)) inline int readint(){
int x;
scanf("%d", &x);
return x;
} inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
} class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int n = Rand(, ), m = Rand(, );
printf("%d %d\n", n, m);
FOR(i, , n){
FOR(j, , m) printf("%c", Rand(, ) + 'a');
putchar('\n');
}
n = Rand(min(, n), ), m = Rand(min(, m), );
printf("%d %d\n", n, m);
FOR(i, , n){
FOR(j, , m) printf("%c", Rand(, ) + 'a');
putchar('\n');
}
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
const int maxn = 1e2 + ;
ll v[][maxn];
ll M;
char s[maxn * maxn];
char* pointer;
ll C[maxn][maxn];
bool isNumber(char c) { return c >= '' && c <= ''; }
ll anayInt(ll dft){
int op = ;
if(*pointer == '+') ++pointer;
if(*pointer == '-') op = -, ++pointer;
if(!isNumber(*pointer)) return op * dft;
char tem[];
int k = ;
while(*pointer <= '' && *pointer >= '') tem[k++] = *pointer, ++pointer;
ll ans = , base = ;
while(k--){
ans += base * (tem[k] - '');
base *= ;
}
return ans * op;
} void anayTerm(){
ll C = anayInt();
if(*pointer != 'n'){
v[][] += (C % M + M) % M;
return;
}
++pointer;
if(*pointer != '^'){
v[][] += (C % M + M) % M;
return;
}
++pointer;
ll E = anayInt();
v[][E] += (C % M + M) % M;
} void anaystr(){
int p = ;
int tem = strlen(s);
FOR(i, , tem - ) if(s[i] != ' ') s[p++] = s[i];
s[p] = '\0';
pointer = s + ;
while(*pointer != '/') ++pointer;
++pointer;
M = anayInt();
pointer = s + ;
do{
anayTerm();
}while(*pointer != ')');
} bool check(int o){
int p = ;
while(p && v[o][p] == ) --p;
return !p;
} ll getSum(int o){
ll ans = ;
FOR(i, , ) ans = (ans + v[o][i]) % M;
return ans;
} void init(){
FOR(i, , ) C[i][i] = C[i][] = % M;
FOR(i, , ){
FOR(j, , i - ) C[i][j] = (C[i - ][j] + C[i - ][j - ]) % M;
}
} int getAns(){
int o = ;
while(!check(o)){
ll tem = getSum(o);
if(tem % M) return ;
int no = o ^ ;
clr(v[no], );
FOR(i, , ){
FOR(j, , i - ) v[no][j] = (v[no][j] + v[o][i] * C[i][j] % M) % M;
}
o = no;
}
return !v[o][];
} //-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int kase = ;
while(gets(s) && s[] != '.'){
clr(v, );
anaystr();
init();
int ok = getAns();
printf("Case %d: %s\n", ++kase, ok ? "Always an integer" : "Not always an integer");
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
8.LA 5059 Play with Stones
关键词：组合游戏，找规律，SG函数
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e9 + ;
const double double_inf = 1e30;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x)) inline int readint(){
int x;
scanf("%d", &x);
return x;
} inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
} class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
int n;
ll a[];
bool solve(){
ll tem = ;
FOR(i, , n){
ll sg = ;
do{
ll t = 1ll << sg;
ll res = a[i] % t;
if(res == (t >> ) - ) break;
++sg;
}while();
tem ^= a[i] / (1ll << sg);
}
return tem == ;
}
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//init(); return 0;
int T = readint();
while(T--){
n = readint();
FOR(i, , n) scanf("%lld", &a[i]);
bool ans = solve();
puts(ans ? "NO" : "YES");
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
9.Uva 11021 Tribles
关键词：概率期望，递推
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e9 + ;
const double double_inf = 1e30;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x)) inline int readint(){
int x;
scanf("%d", &x);
return x;
} inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
} class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
const int maxn = 1e3 + ;
double p[maxn], P[maxn];
int n, m, k;
double power(double x, int p){
double ans = ;
while(p){
if(p & ) ans *= x;
p >>= ;
x = x * x;
}
return ans;
}
double getAns(){
p[] = ;
FOR(i, , m){
p[i] = ;
FOR(j, , n - ) p[i] += P[j] * (. - power(( - p[i - ]), j));
}
return power((. - p[m]), k);
}
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int T = readint(), kase = ;
while(~scanf("%d%d%d", &n, &k, &m)){
FOR(i, , n - ) scanf("%lf", &P[i]);
double ans = getAns();
printf("Case #%d: %.7f\n", ++kase, ans);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
10.Uva10341 Solve It!
关键词：数值方法，高精度
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e9 + ;
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x)) inline int readint(){
int x;
scanf("%d", &x);
return x;
} inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
} class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
double p, q, r, s, t, u;
double f(double x){
return p * exp(-x) + q * sin(x) + r * cos(x) + s * tan(x) + t * x * x + u;
}
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(~scanf("%lf%lf%lf%lf%lf%lf", &p, &q, &r, &s, &t, &u)){
double high = f(), low = f();
if(low > eps || high < -eps){
//dbg2(low, high);
puts("No solution");
}else{
double l = , r = , mid;
while(r - l > eps){
mid = l + (r - l) / ;
double tem = f(mid);
if(tem < ) r = mid;
else l = mid;
}
printf("%.4f\n", mid);
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
11.LA 5009 Error Curves
关键词：数值方法，二分枚举
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define pi acos(-1.)
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e9 + ;
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x)) inline int readint(){
int x;
scanf("%d", &x);
return x;
} inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
} class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
} void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
int n;
const int maxn = 1e4 + ;
pair<pii, int> a[maxn];
double minimum[maxn];
double f(int id, double x){
return a[id].st.st * x * x + a[id].st.nd * x + a[id].nd;
}
double solve(){
double low = 1e20, high = -1e20;
FOR(i, , n){
double tem = f(i, );
maximize(high, tem), minimize(low, tem);
tem = f(i, );
maximize(high, tem), minimize(low, tem);
if(a[i].st.st && -a[i].st.nd >= && -a[i].st.nd <= * a[i].st.st){
tem = f(i, -a[i].st.nd / (double)( * a[i].st.st));
maximize(high, tem), minimize(low, tem);
}
}
FOR(i, , n) if(a[i].st.st)
minimum[i] = ((double)a[i].st.st * a[i].nd * - (double)a[i].st.nd * a[i].st.nd) / ((double) * a[i].st.st);
int times = ;
double mid;
while(times--){
mid = low + (high - low) / ;
double L = -, R = ;
FOR(i, , n){
if(a[i].st.st){
if(minimum[i] >= mid){
maximize(L, ), minimize(R, );
continue;
}
double delta = (double)a[i].st.nd * a[i].st.nd - * (double)a[i].st.st * (a[i].nd - mid);
double x1 = (-a[i].st.nd - sqrt(delta)) / ( * (double)a[i].st.st);
double x2 = (-a[i].st.nd + sqrt(delta)) / ( * (double)a[i].st.st);
maximize(L, x1), minimize(R, x2);
}else{
double y1 = f(i, ), y2 = f(i, );
double _low = min(y1, y2), _high = max(y1, y2);
if(_low >= mid) maximize(L, ), minimize(R, );
else if(_high <= mid) continue;
else if(a[i].st.nd){
double x = (mid - a[i].nd) / a[i].st.nd;
if(a[i].st.nd > ) minimize(R, x);
else maximize(L, x);
}
}
}
if(L >= || R <= || L >= R) low = mid;
else high = mid;
}
return mid;
}
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int T = readint();
while(T--){
n = readint();
FOR(i, , n){
a[i].st.st = readint();
a[i].st.nd = readint();
a[i].nd = readint();
}
double ans = solve();
printf("%.4f\n", ans);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
12.Uva 12304 2D Geometry 110 in 1!
关键词：计算几何，高精度
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define PI acos(-1.)
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x))
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e9 + ;
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
inline int readint(){
int x;
scanf("%d", &x);
return x;
}
inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
}
//Here goes 2d geometry templates
struct Point{
double x, y;
Point(double x = , double y = ) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){
return Vector(A.x + B.x, A.y + B.y);
}
Vector operator - (Point A, Point B){
return Vector(A.x - B.x, A.y - B.y);
}
Vector operator * (Vector A, double p){
return Vector(A.x * p, A.y * p);
}
Vector operator / (Vector A, double p){
return Vector(A.x / p, A.y / p);
}
bool operator < (const Point& a, const Point& b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int dcmp(double x){
if(abs(x) < eps) return ;
return x < ? - : ;
}
bool operator == (const Point& a, const Point& b){
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
}
double Dot(Vector A, Vector B){
return A.x * B.x + A.y * B.y;
}
double Len(Vector A){
return sqrt(Dot(A, A));
}
double Angle(Vector A, Vector B){
return acos(Dot(A, B) / Len(A) / Len(B));
}
double Cross(Vector A, Vector B){
return A.x * B.y - A.y * B.x;
}
double Area2(Point A, Point B, Point C){
return Cross(B - A, C - A);
}
Vector Rotate(Vector A, double rad){
//rotate counterclockwise
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
Vector Normal(Vector A){
double L = Len(A);
return Vector(-A.y / L, A.x / L);
}
void Normallize(Vector &A){
double L = Len(A);
A.x /= L, A.y /= L;
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
double DistanceToLine(Point P, Point A, Point B){
Vector v1 = B - A, v2 = P - A;
return abs(Cross(v1, v2)) / Len(v1);
}
double DistanceSegment(Point P, Point A, Point B){
if(A == B) return Len(P - A);
Vector v1 = B - A, v2 = P - A, v3 = P - B;
if(dcmp(Dot(v1, v2)) < ) return Len(v2);
else if(dcmp(Dot(v1, v3)) > ) return Len(v3);
else return abs(Cross(v1, v2)) / Len(v1);
}
Point GetLineProjection(Point P, Point A, Point B){
Vector v = B - A;
return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2){
//Line1:(a1, a2) Line2:(b1,b2)
double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
}
bool OnSegment(Point p, Point a1, Point a2){
return dcmp(Cross(a1 - p, a2 - p)) == && dcmp(Dot(a1 - p, a2 -p)) < ;
}
Vector GetBisector(Vector v, Vector w){
Normallize(v), Normallize(w);
return Vector((v.x + w.x) / , (v.y + w.y) / );
} bool OnLine(Point p, Point a1, Point a2){
Vector v1 = p - a1, v2 = a2 - a1;
double tem = Cross(v1, v2);
return dcmp(tem) == ;
}
struct Line{
Point p;
Vector v;
Point point(double t){
return Point(p.x + t * v.x, p.y + t * v.y);
}
Line(Point p, Vector v) : p(p), v(v) {}
};
struct Circle{
Point c;
double r;
Circle(Point c, double r) : c(c), r(r) {}
Circle(int x, int y, int _r){
c = Point(x, y);
r = _r;
}
Point point(double a){
return Point(c.x + cos(a) * r, c.y + sin(a) * r);
}
};
int GetLineCircleIntersection(Line L, Circle C, double &t1, double& t2, vector<Point>& sol){
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
double e = a * a + c * c, f = * (a * b + c * d), g = b * b + d * d - C.r * C.r;
double delta = f * f - * e * g;
if(dcmp(delta) < ) return ;
if(dcmp(delta) == ){
t1 = t2 = -f / ( * e); sol.pb(L.point(t1));
return ;
}
t1 = (-f - sqrt(delta)) / ( * e); sol.pb(L.point(t1));
t2 = (-f + sqrt(delta)) / ( * e); sol.pb(L.point(t2));
return ;
}
double angle(Vector v){
return atan2(v.y, v.x);
//(-pi, pi]
}
int GetCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol){
double d = Len(C1.c - C2.c);
if(dcmp(d) == ){
if(dcmp(C1.r - C2.r) == ) return -; //two circle duplicates
return ; //two circles share identical center
}
if(dcmp(C1.r + C2.r - d) < ) return ; //too close
if(dcmp(abs(C1.r - C2.r) - d) > ) return ; //too far away
double a = angle(C2.c - C1.c); // angle of vector(C1, C2)
double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / ( * C1.r * d));
Point p1 = C1.point(a - da), p2 = C1.point(a + da);
sol.pb(p1);
if(p1 == p2) return ;
sol.pb(p2);
return ;
}
int GetPointCircleTangents(Point p, Circle C, Vector* v){
Vector u = C.c - p;
double dist = Len(u);
if(dist < C.r) return ;//p is inside the circle, no tangents
else if(dcmp(dist - C.r) == ){
// p is on the circles, one tangent only
v[] = Rotate(u, PI / );
return ;
}else{
double ang = asin(C.r / dist);
v[] = Rotate(u, -ang);
v[] = Rotate(u, +ang);
return ;
}
}
int GetCircleCircleTangents(Circle A, Circle B, Point* a, Point* b){
//a[i] store point of tangency on Circle A of tangent i
//b[i] store point of tangency on Circle B of tangent i
//six conditions is in consideration
int cnt = ;
if(A.r < B.r) { swap(A, B); swap(a, b); }
int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
int rdiff = A.r - B.r;
int rsum = A.r + B.r;
if(d2 < rdiff * rdiff) return ; // one circle is inside the other
double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
if(d2 == && A.r == B.r) return -; // two circle duplicates
if(d2 == rdiff * rdiff){ // internal tangency
a[cnt] = A.point(base); b[cnt] = B.point(base); cnt++;
return ;
}
double ang = acos((A.r - B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang);
if(d2 == rsum * rsum){
//one internal tangent
a[cnt] = A.point(base);
b[cnt++] = B.point(base + PI);
}else if(d2 > rsum * rsum){
//two internal tangents
double ang = acos((A.r + B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang + PI);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang + PI);
}
return cnt;
}
Point ReadPoint(){
double x, y;
scanf("%lf%lf", &x, &y);
return Point(x, y);
}
Circle ReadCircle(){
double x, y, r;
scanf("%lf%lf%lf", &x, &y, &r);
return Circle(x, y, r);
}
//Here goes 3d geometry templates
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
}
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
int n;
char cmd[];
map<string, int> mapi;
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
mapi.clear();
mapi[string("CircumscribedCircle")] = ;
mapi[string("InscribedCircle")] = ;
mapi[string("TangentLineThroughPoint")] = ;
mapi[string("CircleThroughAPointAndTangentToALineWithRadius")] = ;
mapi[string("CircleTangentToTwoLinesWithRadius")] = ;
mapi[string("CircleTangentToTwoDisjointCirclesWithRadius")] = ;
while(~scanf("%s", cmd)){
int op = mapi[string(cmd)];
if(!op){
Point A = ReadPoint(), B = ReadPoint(), C = ReadPoint();
Point p1 = Point((A.x + B.x) / , (A.y + B.y) / );
Point p2 = Point((A.x + C.x) / , (A.y + C.y) / );
Vector v1 = Normal(B - A), v2 = Normal(C - A);
Point p3 = GetLineIntersection(p1, v1, p2, v2);
double R = Len(p3 - A);
printf("(%.6f,%.6f,%.6f)\n", p3.x, p3.y, R);
}else if(op == ){
Point A = ReadPoint(), B = ReadPoint(), C = ReadPoint();
double a2 = angle(C - A), a1 = angle(B - A);
double a3 = (a1 + a2) / ;
Vector v1 = Vector(cos(a3), sin(a3));
a2 = angle(A - B), a1 = angle(C - B);
a3 = (a2 + a1) / ;
Vector v2 = Vector(cos(a3), sin(a3));
Point p3 = GetLineIntersection(A, v1, B, v2);
double R = DistanceToLine(p3, A, B);
printf("(%.6f,%.6f,%.6f)\n", p3.x, p3.y, R);
}else if(op == ){
Circle A = ReadCircle();
Point p = ReadPoint();
Vector tem[];
int cnt = GetPointCircleTangents(p, A, tem);
putchar('[');
if(cnt == ){
double ang = angle(tem[]);
ang *= / PI;
if(dcmp(ang - ) == ) ang = ;
else if(dcmp(ang) < ) ang += ;
printf("%.6f", ang);
}else if(cnt == ){
double ang1 = angle(tem[]), ang2 = angle(tem[]);
ang1 *= / PI, ang2 *= / PI;
if(dcmp(ang1 - ) == ) ang1 = ;
else if(dcmp(ang1) < ) ang1 += ;
if(dcmp(ang2 - ) == ) ang2 = ;
else if(dcmp(ang2) < ) ang2 += ;
if(ang1 > ang2) swap(ang1, ang2);
printf("%.6f,%.6f", ang1, ang2);
}
puts("]");
}else if(op == ){
Point p = ReadPoint();
Point a1 = ReadPoint(), a2 = ReadPoint();
double R;
scanf("%lf", &R);
double dist = DistanceToLine(p, a1, a2);
if(dcmp( * R - dist) == ){
Point tp = GetLineProjection(p, a1, a2);
Point p3 = Point((tp.x + p.x) / , (tp.y + p.y) / );
printf("[(%.6f,%.6f)]\n", p3.x, p3.y);
}else if(dcmp( * R - dist) < ){
puts("[]");
}else{
if(OnLine(p, a1, a2)){
Vector v1 = Normal(a2 - a1);
Normallize(v1);
Point p3 = Point(p.x + v1.x * R, p.y + v1.y * R);
v1.x = -v1.x, v1.y = -v1.y;
Point p4 = Point(p.x + v1.x * R, p.y + v1.y * R);
if(p4 < p3) swap(p3, p4);
printf("[(%.6f,%.6f),(%.6f,%.6f)]\n", p3.x, p3.y, p4.x, p4.y);
}else{
double ang = acos((dist - R) / R);
Point tp = GetLineProjection(p, a1, a2);
Vector v1 = Rotate(tp - p, ang), v2 = Rotate(tp - p, -ang);
ang = angle(v1);
Point p3 = Point(p.x + R * cos(ang), p.y + R * sin(ang));
ang = angle(v2);
Point p4 = Point(p.x + R * cos(ang), p.y + R * sin(ang));
if(p4 < p3) swap(p3, p4);
printf("[(%.6f,%.6f),(%.6f,%.6f)]\n", p3.x, p3.y, p4.x, p4.y);
}
}
}else if(op == ){
Point a1 = ReadPoint(), a2 = ReadPoint(), b1 = ReadPoint(), b2 = ReadPoint();
double R;
scanf("%lf", &R);
Vector v1 = a2 - a1, v2 = b2 - b1;
int dx[] = {-, -, , }, dy[] = {-, , , -};
Point ans[];
FOR(i, , ){
Vector _v1 = Vector(v1.x * dx[i], v1.y * dx[i]);
Vector _v2 = Vector(v2.x * dy[i], v2.y * dy[i]);
Point p = GetLineIntersection(a1, v1, b1, v2);
double L = R / sin(Angle(_v1, _v2) / );
Vector mid = GetBisector(_v1, _v2);
Normallize(mid);
Point p3 = Point(p.x + L * mid.x, p.y + L * mid.y);
ans[i] = p3;
}
printf("[");
sort(ans, ans + );
FOR(i, , ){
if(i) printf(",");
printf("(%.6f,%.6f)", ans[i].x, ans[i].y);
}
printf("]\n");
}else if(op == ){
Circle C1 = ReadCircle(), C2 = ReadCircle();
double R;
scanf("%lf", &R);
double dist = Len(C1.c - C2.c);
printf("[");
if(dcmp(dist - C1.r - C2.r - * R) == ){
Line l = Line(C2.c, C1.c - C2.c);
Point p3 = l.point((C2.r + R) / Len(C1.c - C2.c));
printf("(%.6f,%.6f)", p3.x, p3.y);
}else if(dcmp(dist - C1.r - C2.r - * R) < ){
double _a = R + C2.r, _b = Len(C1.c - C2.c), _c = C1.r + R;
double da = acos((_a * _a + _b * _b - _c * _c) / ( * _a * _b));
double ang = angle(C1.c - C2.c);
double ang1 = ang + da;
Point p3 = Point(C2.c.x + cos(ang1) * _a, C2.c.y + sin(ang1) * _a);
double ang2 = ang - da;
Point p4 = Point(C2.c.x + cos(ang2) * _a, C2.c.y + sin(ang2) * _a);
if(p4 < p3) swap(p3, p4);
printf("(%.6f,%.6f),(%.6f,%.6f)", p3.x, p3.y, p4.x, p4.y);
}
puts("]");
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
13.Uva 10561 Treblecross
关键词：组合游戏，SG函数
题意：在一个一维棋盘上放石子，若使得三个石子连续，则胜。初始时棋盘上没有三个连续的石子。
分析：P状态是不难判定的，但如果把所有石子摆放情况当作一个状态，是没法进行处理的。注意到为了避免进入P态，任何石子其左右2个位置应该被空出。
那么我们把这段当作禁止区间，把完整游戏分割为若干独立的子游戏，状态就是连续空出的格子长度。这样用SG函数就可以很方便地求解。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define PI acos(-1.)
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x))
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e9 + ;
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
inline int readint(){
int x;
scanf("%d", &x);
return x;
}
inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
}
//Here goes 2d geometry templates
struct Point{
double x, y;
Point(double x = , double y = ) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){
return Vector(A.x + B.x, A.y + B.y);
}
Vector operator - (Point A, Point B){
return Vector(A.x - B.x, A.y - B.y);
}
Vector operator * (Vector A, double p){
return Vector(A.x * p, A.y * p);
}
Vector operator / (Vector A, double p){
return Vector(A.x / p, A.y / p);
}
bool operator < (const Point& a, const Point& b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int dcmp(double x){
if(abs(x) < eps) return ;
return x < ? - : ;
}
bool operator == (const Point& a, const Point& b){
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
}
double Dot(Vector A, Vector B){
return A.x * B.x + A.y * B.y;
}
double Len(Vector A){
return sqrt(Dot(A, A));
}
double Angle(Vector A, Vector B){
return acos(Dot(A, B) / Len(A) / Len(B));
}
double Cross(Vector A, Vector B){
return A.x * B.y - A.y * B.x;
}
double Area2(Point A, Point B, Point C){
return Cross(B - A, C - A);
}
Vector Rotate(Vector A, double rad){
//rotate counterclockwise
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
Vector Normal(Vector A){
double L = Len(A);
return Vector(-A.y / L, A.x / L);
}
void Normallize(Vector &A){
double L = Len(A);
A.x /= L, A.y /= L;
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
double DistanceToLine(Point P, Point A, Point B){
Vector v1 = B - A, v2 = P - A;
return abs(Cross(v1, v2)) / Len(v1);
}
double DistanceToSegment(Point P, Point A, Point B){
if(A == B) return Len(P - A);
Vector v1 = B - A, v2 = P - A, v3 = P - B;
if(dcmp(Dot(v1, v2)) < ) return Len(v2);
else if(dcmp(Dot(v1, v3)) > ) return Len(v3);
else return abs(Cross(v1, v2)) / Len(v1);
}
Point GetLineProjection(Point P, Point A, Point B){
Vector v = B - A;
return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2){
//Line1:(a1, a2) Line2:(b1,b2)
double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
}
bool OnSegment(Point p, Point a1, Point a2){
return dcmp(Cross(a1 - p, a2 - p)) == && dcmp(Dot(a1 - p, a2 -p)) < ;
}
Vector GetBisector(Vector v, Vector w){
Normallize(v), Normallize(w);
return Vector((v.x + w.x) / , (v.y + w.y) / );
} bool OnLine(Point p, Point a1, Point a2){
Vector v1 = p - a1, v2 = a2 - a1;
double tem = Cross(v1, v2);
return dcmp(tem) == ;
}
struct Line{
Point p;
Vector v;
Point point(double t){
return Point(p.x + t * v.x, p.y + t * v.y);
}
Line(Point p, Vector v) : p(p), v(v) {}
};
struct Circle{
Point c;
double r;
Circle(Point c, double r) : c(c), r(r) {}
Circle(int x, int y, int _r){
c = Point(x, y);
r = _r;
}
Point point(double a){
return Point(c.x + cos(a) * r, c.y + sin(a) * r);
}
};
int GetLineCircleIntersection(Line L, Circle C, double &t1, double& t2, vector<Point>& sol){
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
double e = a * a + c * c, f = * (a * b + c * d), g = b * b + d * d - C.r * C.r;
double delta = f * f - * e * g;
if(dcmp(delta) < ) return ;
if(dcmp(delta) == ){
t1 = t2 = -f / ( * e); sol.pb(L.point(t1));
return ;
}
t1 = (-f - sqrt(delta)) / ( * e); sol.pb(L.point(t1));
t2 = (-f + sqrt(delta)) / ( * e); sol.pb(L.point(t2));
return ;
}
double angle(Vector v){
return atan2(v.y, v.x);
//(-pi, pi]
}
int GetCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol){
double d = Len(C1.c - C2.c);
if(dcmp(d) == ){
if(dcmp(C1.r - C2.r) == ) return -; //two circle duplicates
return ; //two circles share identical center
}
if(dcmp(C1.r + C2.r - d) < ) return ; //too close
if(dcmp(abs(C1.r - C2.r) - d) > ) return ; //too far away
double a = angle(C2.c - C1.c); // angle of vector(C1, C2)
double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / ( * C1.r * d));
Point p1 = C1.point(a - da), p2 = C1.point(a + da);
sol.pb(p1);
if(p1 == p2) return ;
sol.pb(p2);
return ;
}
int GetPointCircleTangents(Point p, Circle C, Vector* v){
Vector u = C.c - p;
double dist = Len(u);
if(dist < C.r) return ;//p is inside the circle, no tangents
else if(dcmp(dist - C.r) == ){
// p is on the circles, one tangent only
v[] = Rotate(u, PI / );
return ;
}else{
double ang = asin(C.r / dist);
v[] = Rotate(u, -ang);
v[] = Rotate(u, +ang);
return ;
}
}
int GetCircleCircleTangents(Circle A, Circle B, Point* a, Point* b){
//a[i] store point of tangency on Circle A of tangent i
//b[i] store point of tangency on Circle B of tangent i
//six conditions is in consideration
int cnt = ;
if(A.r < B.r) { swap(A, B); swap(a, b); }
int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
int rdiff = A.r - B.r;
int rsum = A.r + B.r;
if(d2 < rdiff * rdiff) return ; // one circle is inside the other
double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
if(d2 == && A.r == B.r) return -; // two circle duplicates
if(d2 == rdiff * rdiff){ // internal tangency
a[cnt] = A.point(base); b[cnt] = B.point(base); cnt++;
return ;
}
double ang = acos((A.r - B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang);
if(d2 == rsum * rsum){
//one internal tangent
a[cnt] = A.point(base);
b[cnt++] = B.point(base + PI);
}else if(d2 > rsum * rsum){
//two internal tangents
double ang = acos((A.r + B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang + PI);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang + PI);
}
return cnt;
}
Point ReadPoint(){
double x, y;
scanf("%lf%lf", &x, &y);
return Point(x, y);
}
Circle ReadCircle(){
double x, y, r;
scanf("%lf%lf%lf", &x, &y, &r);
return Circle(x, y, r);
}
//Here goes 3d geometry templates
struct Point3{
double x, y, z;
Point3(double x = , double y = , double z = ) : x(x), y(y), z(z) {}
};
typedef Point3 Vector3;
Vector3 operator + (Vector3 A, Vector3 B){
return Vector3(A.x + B.x, A.y + B.y, A.z + B.z);
}
Vector3 operator - (Vector3 A, Vector3 B){
return Vector3(A.x - B.x, A.y - B.y, A.z - B.z);
}
Vector3 operator * (Vector3 A, double p){
return Vector3(A.x * p, A.y * p, A.z * p);
}
Vector3 operator / (Vector3 A, double p){
return Vector3(A.x / p, A.y / p, A.z / p);
}
double Dot3(Vector3 A, Vector3 B){
return A.x * B.x + A.y * B.y + A.z * B.z;
}
double Len3(Vector3 A){
return sqrt(Dot3(A, A));
}
double Angle3(Vector3 A, Vector3 B){
return acos(Dot3(A, B) / Len3(A) / Len3(B));
}
double DistanceToPlane(const Point3& p, const Point3 &p0, const Vector3& n){
return abs(Dot3(p - p0, n));
}
Point3 GetPlaneProjection(const Point3 &p, const Point3 &p0, const Vector3 &n){
return p - n * Dot3(p - p0, n);
}
Point3 GetLinePlaneIntersection(Point3 p1, Point3 p2, Point3 p0, Vector3 n){
Vector3 v = p2 - p1;
double t = (Dot3(n, p0 - p1) / Dot3(n, p2 - p1));
return p1 + v * t;//if t in range [0, 1], intersection on segment
}
Vector3 Cross(Vector3 A, Vector3 B){
return Vector3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}
double Area3(Point3 A, Point3 B, Point3 C){
return Len3(Cross(B - A, C - A));
}
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
}
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
const int maxn = 3e2 + ;
int dp[maxn];
char s[maxn], s1[maxn];
int _ans[maxn], k;
pii buf[maxn];
int k1;
int n;
bool vis[maxn]; void solve(){
k = ;
FOR(i, , n - ){
if(s[i] != '.') continue;
if(i - >= && s[i - ] == 'X' && s[i - ] == 'X'){
_ans[k++] = i;
continue;
}else if(i - >= && i + < n && s[i - ] == 'X' && s[i + ] == 'X'){
_ans[k++] = i;
continue;
}else if(i + < n && s[i + ] == 'X' && s[i + ] == 'X'){
_ans[k++] = i;
continue;
}
}
if(k){
puts("WINNING");
printf("%d", _ans[] + );
FOR(i, , k - ) printf(" %d", _ans[i] + );
printf("\n");
return;
}else{
int ans = ;
memcpy(s1, s, sizeof(s));
FOR(i, , n - ){
if(s[i] == '.') continue;
int l = max(, i - ), r = min(n - , i + );
FOR(j, l, r) s1[j] = 'P';
}
memcpy(s, s1, sizeof(s1));
k1 = ;
for(int i = ; i < n; ){
if(s[i] != '.'){
++i;
continue;
}else{
int j = i;
while(j < n && s[j] == '.') ++j;
ans ^= dp[j - i];
buf[k1++] = mp(i, j - i);
i = j;
}
}
if(!ans){
puts("LOSING\n");
}else{
k = ;
FOR(i, , k1 - ){
int tans = ans;
tans ^= dp[buf[i].nd];
FOR(j, , buf[i].nd - ){
int ttans = tans;
ttans ^= dp[max(, j - )];
ttans ^= dp[max(, buf[i].nd - j - )];
if(!ttans) _ans[k++] = buf[i].st + j;
}
}
puts("WINNING");
printf("%d", _ans[] + );
FOR(i, , k - ) printf(" %d", _ans[i] + );
printf("\n");
}
}
} //-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
dp[] = ;
FOR(i, , ){
clr(vis, );
FOR(j, , i - ){
int lhs = dp[max(, j - )];
int rhs = dp[max(, i - j - )];
vis[lhs ^ rhs] = ;
}
int bg = ;
while(vis[bg]) ++bg;
dp[i] = bg;
}
int T = readint();
//FOR(i, 1, 9) DP(i);
while(T--){
n = readstr(s);
solve();
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
14.Uva 11762 Race to 1
关键词：数学期望，递推，素数分解
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define PI acos(-1.)
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x))
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e9 + ;
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
inline int readint(){
int x;
scanf("%d", &x);
return x;
}
inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
}
//Here goes 2d geometry templates
struct Point{
double x, y;
Point(double x = , double y = ) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){
return Vector(A.x + B.x, A.y + B.y);
}
Vector operator - (Point A, Point B){
return Vector(A.x - B.x, A.y - B.y);
}
Vector operator * (Vector A, double p){
return Vector(A.x * p, A.y * p);
}
Vector operator / (Vector A, double p){
return Vector(A.x / p, A.y / p);
}
bool operator < (const Point& a, const Point& b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int dcmp(double x){
if(abs(x) < eps) return ;
return x < ? - : ;
}
bool operator == (const Point& a, const Point& b){
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
}
double Dot(Vector A, Vector B){
return A.x * B.x + A.y * B.y;
}
double Len(Vector A){
return sqrt(Dot(A, A));
}
double Angle(Vector A, Vector B){
return acos(Dot(A, B) / Len(A) / Len(B));
}
double Cross(Vector A, Vector B){
return A.x * B.y - A.y * B.x;
}
double Area2(Point A, Point B, Point C){
return Cross(B - A, C - A);
}
Vector Rotate(Vector A, double rad){
//rotate counterclockwise
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
Vector Normal(Vector A){
double L = Len(A);
return Vector(-A.y / L, A.x / L);
}
void Normallize(Vector &A){
double L = Len(A);
A.x /= L, A.y /= L;
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
double DistanceToLine(Point P, Point A, Point B){
Vector v1 = B - A, v2 = P - A;
return abs(Cross(v1, v2)) / Len(v1);
}
double DistanceToSegment(Point P, Point A, Point B){
if(A == B) return Len(P - A);
Vector v1 = B - A, v2 = P - A, v3 = P - B;
if(dcmp(Dot(v1, v2)) < ) return Len(v2);
else if(dcmp(Dot(v1, v3)) > ) return Len(v3);
else return abs(Cross(v1, v2)) / Len(v1);
}
Point GetLineProjection(Point P, Point A, Point B){
Vector v = B - A;
return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2){
//Line1:(a1, a2) Line2:(b1,b2)
double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
}
bool OnSegment(Point p, Point a1, Point a2){
return dcmp(Cross(a1 - p, a2 - p)) == && dcmp(Dot(a1 - p, a2 -p)) < ;
}
Vector GetBisector(Vector v, Vector w){
Normallize(v), Normallize(w);
return Vector((v.x + w.x) / , (v.y + w.y) / );
} bool OnLine(Point p, Point a1, Point a2){
Vector v1 = p - a1, v2 = a2 - a1;
double tem = Cross(v1, v2);
return dcmp(tem) == ;
}
struct Line{
Point p;
Vector v;
Point point(double t){
return Point(p.x + t * v.x, p.y + t * v.y);
}
Line(Point p, Vector v) : p(p), v(v) {}
};
struct Circle{
Point c;
double r;
Circle(Point c, double r) : c(c), r(r) {}
Circle(int x, int y, int _r){
c = Point(x, y);
r = _r;
}
Point point(double a){
return Point(c.x + cos(a) * r, c.y + sin(a) * r);
}
};
int GetLineCircleIntersection(Line L, Circle C, double &t1, double& t2, vector<Point>& sol){
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
double e = a * a + c * c, f = * (a * b + c * d), g = b * b + d * d - C.r * C.r;
double delta = f * f - * e * g;
if(dcmp(delta) < ) return ;
if(dcmp(delta) == ){
t1 = t2 = -f / ( * e); sol.pb(L.point(t1));
return ;
}
t1 = (-f - sqrt(delta)) / ( * e); sol.pb(L.point(t1));
t2 = (-f + sqrt(delta)) / ( * e); sol.pb(L.point(t2));
return ;
}
double angle(Vector v){
return atan2(v.y, v.x);
//(-pi, pi]
}
int GetCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol){
double d = Len(C1.c - C2.c);
if(dcmp(d) == ){
if(dcmp(C1.r - C2.r) == ) return -; //two circle duplicates
return ; //two circles share identical center
}
if(dcmp(C1.r + C2.r - d) < ) return ; //too close
if(dcmp(abs(C1.r - C2.r) - d) > ) return ; //too far away
double a = angle(C2.c - C1.c); // angle of vector(C1, C2)
double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / ( * C1.r * d));
Point p1 = C1.point(a - da), p2 = C1.point(a + da);
sol.pb(p1);
if(p1 == p2) return ;
sol.pb(p2);
return ;
}
int GetPointCircleTangents(Point p, Circle C, Vector* v){
Vector u = C.c - p;
double dist = Len(u);
if(dist < C.r) return ;//p is inside the circle, no tangents
else if(dcmp(dist - C.r) == ){
// p is on the circles, one tangent only
v[] = Rotate(u, PI / );
return ;
}else{
double ang = asin(C.r / dist);
v[] = Rotate(u, -ang);
v[] = Rotate(u, +ang);
return ;
}
}
int GetCircleCircleTangents(Circle A, Circle B, Point* a, Point* b){
//a[i] store point of tangency on Circle A of tangent i
//b[i] store point of tangency on Circle B of tangent i
//six conditions is in consideration
int cnt = ;
if(A.r < B.r) { swap(A, B); swap(a, b); }
int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
int rdiff = A.r - B.r;
int rsum = A.r + B.r;
if(d2 < rdiff * rdiff) return ; // one circle is inside the other
double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
if(d2 == && A.r == B.r) return -; // two circle duplicates
if(d2 == rdiff * rdiff){ // internal tangency
a[cnt] = A.point(base); b[cnt] = B.point(base); cnt++;
return ;
}
double ang = acos((A.r - B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang);
if(d2 == rsum * rsum){
//one internal tangent
a[cnt] = A.point(base);
b[cnt++] = B.point(base + PI);
}else if(d2 > rsum * rsum){
//two internal tangents
double ang = acos((A.r + B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang + PI);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang + PI);
}
return cnt;
}
Point ReadPoint(){
double x, y;
scanf("%lf%lf", &x, &y);
return Point(x, y);
}
Circle ReadCircle(){
double x, y, r;
scanf("%lf%lf%lf", &x, &y, &r);
return Circle(x, y, r);
}
//Here goes 3d geometry templates
struct Point3{
double x, y, z;
Point3(double x = , double y = , double z = ) : x(x), y(y), z(z) {}
};
typedef Point3 Vector3;
Vector3 operator + (Vector3 A, Vector3 B){
return Vector3(A.x + B.x, A.y + B.y, A.z + B.z);
}
Vector3 operator - (Vector3 A, Vector3 B){
return Vector3(A.x - B.x, A.y - B.y, A.z - B.z);
}
Vector3 operator * (Vector3 A, double p){
return Vector3(A.x * p, A.y * p, A.z * p);
}
Vector3 operator / (Vector3 A, double p){
return Vector3(A.x / p, A.y / p, A.z / p);
}
double Dot3(Vector3 A, Vector3 B){
return A.x * B.x + A.y * B.y + A.z * B.z;
}
double Len3(Vector3 A){
return sqrt(Dot3(A, A));
}
double Angle3(Vector3 A, Vector3 B){
return acos(Dot3(A, B) / Len3(A) / Len3(B));
}
double DistanceToPlane(const Point3& p, const Point3 &p0, const Vector3& n){
return abs(Dot3(p - p0, n));
}
Point3 GetPlaneProjection(const Point3 &p, const Point3 &p0, const Vector3 &n){
return p - n * Dot3(p - p0, n);
}
Point3 GetLinePlaneIntersection(Point3 p1, Point3 p2, Point3 p0, Vector3 n){
Vector3 v = p2 - p1;
double t = (Dot3(n, p0 - p1) / Dot3(n, p2 - p1));
return p1 + v * t;//if t in range [0, 1], intersection on segment
}
Vector3 Cross(Vector3 A, Vector3 B){
return Vector3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}
double Area3(Point3 A, Point3 B, Point3 C){
return Len3(Cross(B - A, C - A));
}
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
}
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
const int maxn = 1e6 + ;
int n;
int prime[maxn], k;
int cnt_prime[maxn];
bool vis[maxn];
double dp[maxn];
bool is_prime[maxn];
int p[], k1;
void init(){
k = ;
prime[k++] = ;
is_prime[] = ;
clr(cnt_prime, ), clr(vis, );
cnt_prime[] = ;
for(int i = ; i < maxn; i += ){
if(vis[i]) continue;
prime[k++] = i, cnt_prime[i] = , is_prime[i] = ;
for(int j = i; j < maxn; j += i) vis[j] = ;
}
cnt_prime[] = ;
FOR(i, , maxn - ) cnt_prime[i] += cnt_prime[i - ];
clr(vis, );
vis[] = , dp[] = ;
}
double DP(int x){
if(vis[x]) return dp[x];
vis[x] = ;
k1 = ;
double tem = ;
int x1 = x;
int cnt = ;
int mid = (int)sqrt(x1);
for(int i = ; prime[i] <= mid; i++){
if(x1 % prime[i]) continue;
tem += DP(x / prime[i]);
++cnt;
while(x1 % prime[i] == ) x1 /= prime[i];
}
if(x1 > ) ++cnt, tem += DP(x / x1);
tem *= . / cnt_prime[x];
tem += ;
tem *= cnt_prime[x] / (double)cnt;
return dp[x] = tem;
}
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
init();
int T = readint(), kase = ;
while(T--){
n = readint();
double ans = DP(n);
printf("Case %d: %.10f\n", ++kase, ans);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
15.LA 11427 Expect the Expected
关键词：数学期望，递推
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define PI acos(-1.)
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x))
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const int mod = 1e9 + ;
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
inline int readint(){
int x;
scanf("%d", &x);
return x;
}
inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
}
//Here goes 2d geometry templates
struct Point{
double x, y;
Point(double x = , double y = ) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){
return Vector(A.x + B.x, A.y + B.y);
}
Vector operator - (Point A, Point B){
return Vector(A.x - B.x, A.y - B.y);
}
Vector operator * (Vector A, double p){
return Vector(A.x * p, A.y * p);
}
Vector operator / (Vector A, double p){
return Vector(A.x / p, A.y / p);
}
bool operator < (const Point& a, const Point& b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int dcmp(double x){
if(abs(x) < eps) return ;
return x < ? - : ;
}
bool operator == (const Point& a, const Point& b){
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
}
double Dot(Vector A, Vector B){
return A.x * B.x + A.y * B.y;
}
double Len(Vector A){
return sqrt(Dot(A, A));
}
double Angle(Vector A, Vector B){
return acos(Dot(A, B) / Len(A) / Len(B));
}
double Cross(Vector A, Vector B){
return A.x * B.y - A.y * B.x;
}
double Area2(Point A, Point B, Point C){
return Cross(B - A, C - A);
}
Vector Rotate(Vector A, double rad){
//rotate counterclockwise
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
Vector Normal(Vector A){
double L = Len(A);
return Vector(-A.y / L, A.x / L);
}
void Normallize(Vector &A){
double L = Len(A);
A.x /= L, A.y /= L;
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
double DistanceToLine(Point P, Point A, Point B){
Vector v1 = B - A, v2 = P - A;
return abs(Cross(v1, v2)) / Len(v1);
}
double DistanceToSegment(Point P, Point A, Point B){
if(A == B) return Len(P - A);
Vector v1 = B - A, v2 = P - A, v3 = P - B;
if(dcmp(Dot(v1, v2)) < ) return Len(v2);
else if(dcmp(Dot(v1, v3)) > ) return Len(v3);
else return abs(Cross(v1, v2)) / Len(v1);
}
Point GetLineProjection(Point P, Point A, Point B){
Vector v = B - A;
return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2){
//Line1:(a1, a2) Line2:(b1,b2)
double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
}
bool OnSegment(Point p, Point a1, Point a2){
return dcmp(Cross(a1 - p, a2 - p)) == && dcmp(Dot(a1 - p, a2 -p)) < ;
}
Vector GetBisector(Vector v, Vector w){
Normallize(v), Normallize(w);
return Vector((v.x + w.x) / , (v.y + w.y) / );
} bool OnLine(Point p, Point a1, Point a2){
Vector v1 = p - a1, v2 = a2 - a1;
double tem = Cross(v1, v2);
return dcmp(tem) == ;
}
struct Line{
Point p;
Vector v;
Point point(double t){
return Point(p.x + t * v.x, p.y + t * v.y);
}
Line(Point p, Vector v) : p(p), v(v) {}
};
struct Circle{
Point c;
double r;
Circle(Point c, double r) : c(c), r(r) {}
Circle(int x, int y, int _r){
c = Point(x, y);
r = _r;
}
Point point(double a){
return Point(c.x + cos(a) * r, c.y + sin(a) * r);
}
};
int GetLineCircleIntersection(Line L, Circle C, double &t1, double& t2, vector<Point>& sol){
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
double e = a * a + c * c, f = * (a * b + c * d), g = b * b + d * d - C.r * C.r;
double delta = f * f - * e * g;
if(dcmp(delta) < ) return ;
if(dcmp(delta) == ){
t1 = t2 = -f / ( * e); sol.pb(L.point(t1));
return ;
}
t1 = (-f - sqrt(delta)) / ( * e); sol.pb(L.point(t1));
t2 = (-f + sqrt(delta)) / ( * e); sol.pb(L.point(t2));
return ;
}
double angle(Vector v){
return atan2(v.y, v.x);
//(-pi, pi]
}
int GetCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol){
double d = Len(C1.c - C2.c);
if(dcmp(d) == ){
if(dcmp(C1.r - C2.r) == ) return -; //two circle duplicates
return ; //two circles share identical center
}
if(dcmp(C1.r + C2.r - d) < ) return ; //too close
if(dcmp(abs(C1.r - C2.r) - d) > ) return ; //too far away
double a = angle(C2.c - C1.c); // angle of vector(C1, C2)
double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / ( * C1.r * d));
Point p1 = C1.point(a - da), p2 = C1.point(a + da);
sol.pb(p1);
if(p1 == p2) return ;
sol.pb(p2);
return ;
}
int GetPointCircleTangents(Point p, Circle C, Vector* v){
Vector u = C.c - p;
double dist = Len(u);
if(dist < C.r) return ;//p is inside the circle, no tangents
else if(dcmp(dist - C.r) == ){
// p is on the circles, one tangent only
v[] = Rotate(u, PI / );
return ;
}else{
double ang = asin(C.r / dist);
v[] = Rotate(u, -ang);
v[] = Rotate(u, +ang);
return ;
}
}
int GetCircleCircleTangents(Circle A, Circle B, Point* a, Point* b){
//a[i] store point of tangency on Circle A of tangent i
//b[i] store point of tangency on Circle B of tangent i
//six conditions is in consideration
int cnt = ;
if(A.r < B.r) { swap(A, B); swap(a, b); }
int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
int rdiff = A.r - B.r;
int rsum = A.r + B.r;
if(d2 < rdiff * rdiff) return ; // one circle is inside the other
double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
if(d2 == && A.r == B.r) return -; // two circle duplicates
if(d2 == rdiff * rdiff){ // internal tangency
a[cnt] = A.point(base); b[cnt] = B.point(base); cnt++;
return ;
}
double ang = acos((A.r - B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang);
if(d2 == rsum * rsum){
//one internal tangent
a[cnt] = A.point(base);
b[cnt++] = B.point(base + PI);
}else if(d2 > rsum * rsum){
//two internal tangents
double ang = acos((A.r + B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang + PI);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang + PI);
}
return cnt;
}
Point ReadPoint(){
double x, y;
scanf("%lf%lf", &x, &y);
return Point(x, y);
}
Circle ReadCircle(){
double x, y, r;
scanf("%lf%lf%lf", &x, &y, &r);
return Circle(x, y, r);
}
//Here goes 3d geometry templates
struct Point3{
double x, y, z;
Point3(double x = , double y = , double z = ) : x(x), y(y), z(z) {}
};
typedef Point3 Vector3;
Vector3 operator + (Vector3 A, Vector3 B){
return Vector3(A.x + B.x, A.y + B.y, A.z + B.z);
}
Vector3 operator - (Vector3 A, Vector3 B){
return Vector3(A.x - B.x, A.y - B.y, A.z - B.z);
}
Vector3 operator * (Vector3 A, double p){
return Vector3(A.x * p, A.y * p, A.z * p);
}
Vector3 operator / (Vector3 A, double p){
return Vector3(A.x / p, A.y / p, A.z / p);
}
double Dot3(Vector3 A, Vector3 B){
return A.x * B.x + A.y * B.y + A.z * B.z;
}
double Len3(Vector3 A){
return sqrt(Dot3(A, A));
}
double Angle3(Vector3 A, Vector3 B){
return acos(Dot3(A, B) / Len3(A) / Len3(B));
}
double DistanceToPlane(const Point3& p, const Point3 &p0, const Vector3& n){
return abs(Dot3(p - p0, n));
}
Point3 GetPlaneProjection(const Point3 &p, const Point3 &p0, const Vector3 &n){
return p - n * Dot3(p - p0, n);
}
Point3 GetLinePlaneIntersection(Point3 p1, Point3 p2, Point3 p0, Vector3 n){
Vector3 v = p2 - p1;
double t = (Dot3(n, p0 - p1) / Dot3(n, p2 - p1));
return p1 + v * t;//if t in range [0, 1], intersection on segment
}
Vector3 Cross(Vector3 A, Vector3 B){
return Vector3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}
double Area3(Point3 A, Point3 B, Point3 C){
return Len3(Cross(B - A, C - A));
}
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
}
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
//-------------------------------------------------------------------------
const int maxn = 1e2 + ;
pii p;
int n;
double dp[maxn][maxn];
double _p;
int lim[maxn];
double ans[maxn][maxn];
char s[];
void dealstr(){
char tem[];
char *pointer = s;
int k = ;
while(*pointer >= '' && *pointer <= '') tem[k++] = *pointer, ++pointer;
int base = , cur = ;
ROF(i, k - , ) cur += base * (tem[i] - ''), base *= ;
p.st = cur;
++pointer, k = ;
while(*pointer >= '' && *pointer <= '') tem[k++] = *pointer, ++pointer;
base = , cur = ;
ROF(i, k - , ) cur += base * (tem[i] - ''), base *= ;
p.nd = cur;
}
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int T = readint(), kase = ;
while(T--){
scanf("%s", s);
dealstr();
scanf("%d", &n);
_p = (double)p.st / p.nd;
dp[][] = - _p, dp[][] = _p;
FOR(i, , n){
dp[i][] = dp[i - ][] * ( - _p);
FOR(j, , i) dp[i][j] = (dp[i - ][j] * ( - _p) + dp[i - ][j - ] * _p);
}
FOR(i, , n) lim[i] = p.st * i / p.nd;
ans[][] = - _p;
ans[][] = _p;
FOR(i, , n){
FOR(j, , lim[i]) ans[i][j] = ;
FOR(j, , lim[i - ]){
ans[i][j] += ans[i - ][j] * ( - _p);
if(j + <= lim[i]) ans[i][j + ] += ans[i - ][j] * _p;
}
}
double q = ;
FOR(i, , lim[n]) q += ans[n][i];
//dbg(1 - q);
double _ans = . / q;
printf("Case #%d: %d\n", ++kase, (int)_ans);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
16.LA 3485 Bridge
关键词：数值分析，数论
提示：此题有坑点，另外注意合理转换问题提高精度
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define PI acos(-1.)
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x))
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
inline int readint(){
int x;
scanf("%d", &x);
return x;
}
inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
}
//Here goes 2d geometry templates
struct Point{
double x, y;
Point(double x = , double y = ) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){
return Vector(A.x + B.x, A.y + B.y);
}
Vector operator - (Point A, Point B){
return Vector(A.x - B.x, A.y - B.y);
}
Vector operator * (Vector A, double p){
return Vector(A.x * p, A.y * p);
}
Vector operator / (Vector A, double p){
return Vector(A.x / p, A.y / p);
}
bool operator < (const Point& a, const Point& b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int dcmp(double x){
if(abs(x) < eps) return ;
return x < ? - : ;
}
bool operator == (const Point& a, const Point& b){
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
}
double Dot(Vector A, Vector B){
return A.x * B.x + A.y * B.y;
}
double Len(Vector A){
return sqrt(Dot(A, A));
}
double Angle(Vector A, Vector B){
return acos(Dot(A, B) / Len(A) / Len(B));
}
double Cross(Vector A, Vector B){
return A.x * B.y - A.y * B.x;
}
double Area2(Point A, Point B, Point C){
return Cross(B - A, C - A);
}
Vector Rotate(Vector A, double rad){
//rotate counterclockwise
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
Vector Normal(Vector A){
double L = Len(A);
return Vector(-A.y / L, A.x / L);
}
void Normallize(Vector &A){
double L = Len(A);
A.x /= L, A.y /= L;
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
double DistanceToLine(Point P, Point A, Point B){
Vector v1 = B - A, v2 = P - A;
return abs(Cross(v1, v2)) / Len(v1);
}
double DistanceToSegment(Point P, Point A, Point B){
if(A == B) return Len(P - A);
Vector v1 = B - A, v2 = P - A, v3 = P - B;
if(dcmp(Dot(v1, v2)) < ) return Len(v2);
else if(dcmp(Dot(v1, v3)) > ) return Len(v3);
else return abs(Cross(v1, v2)) / Len(v1);
}
Point GetLineProjection(Point P, Point A, Point B){
Vector v = B - A;
return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2){
//Line1:(a1, a2) Line2:(b1,b2)
double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
}
bool OnSegment(Point p, Point a1, Point a2){
return dcmp(Cross(a1 - p, a2 - p)) == && dcmp(Dot(a1 - p, a2 -p)) < ;
}
Vector GetBisector(Vector v, Vector w){
Normallize(v), Normallize(w);
return Vector((v.x + w.x) / , (v.y + w.y) / );
} bool OnLine(Point p, Point a1, Point a2){
Vector v1 = p - a1, v2 = a2 - a1;
double tem = Cross(v1, v2);
return dcmp(tem) == ;
}
struct Line{
Point p;
Vector v;
Point point(double t){
return Point(p.x + t * v.x, p.y + t * v.y);
}
Line(Point p, Vector v) : p(p), v(v) {}
};
struct Circle{
Point c;
double r;
Circle(Point c, double r) : c(c), r(r) {}
Circle(int x, int y, int _r){
c = Point(x, y);
r = _r;
}
Point point(double a){
return Point(c.x + cos(a) * r, c.y + sin(a) * r);
}
};
int GetLineCircleIntersection(Line L, Circle C, double &t1, double& t2, vector<Point>& sol){
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
double e = a * a + c * c, f = * (a * b + c * d), g = b * b + d * d - C.r * C.r;
double delta = f * f - * e * g;
if(dcmp(delta) < ) return ;
if(dcmp(delta) == ){
t1 = t2 = -f / ( * e); sol.pb(L.point(t1));
return ;
}
t1 = (-f - sqrt(delta)) / ( * e); sol.pb(L.point(t1));
t2 = (-f + sqrt(delta)) / ( * e); sol.pb(L.point(t2));
return ;
}
double angle(Vector v){
return atan2(v.y, v.x);
//(-pi, pi]
}
int GetCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol){
double d = Len(C1.c - C2.c);
if(dcmp(d) == ){
if(dcmp(C1.r - C2.r) == ) return -; //two circle duplicates
return ; //two circles share identical center
}
if(dcmp(C1.r + C2.r - d) < ) return ; //too close
if(dcmp(abs(C1.r - C2.r) - d) > ) return ; //too far away
double a = angle(C2.c - C1.c); // angle of vector(C1, C2)
double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / ( * C1.r * d));
Point p1 = C1.point(a - da), p2 = C1.point(a + da);
sol.pb(p1);
if(p1 == p2) return ;
sol.pb(p2);
return ;
}
int GetPointCircleTangents(Point p, Circle C, Vector* v){
Vector u = C.c - p;
double dist = Len(u);
if(dist < C.r) return ;//p is inside the circle, no tangents
else if(dcmp(dist - C.r) == ){
// p is on the circles, one tangent only
v[] = Rotate(u, PI / );
return ;
}else{
double ang = asin(C.r / dist);
v[] = Rotate(u, -ang);
v[] = Rotate(u, +ang);
return ;
}
}
int GetCircleCircleTangents(Circle A, Circle B, Point* a, Point* b){
//a[i] store point of tangency on Circle A of tangent i
//b[i] store point of tangency on Circle B of tangent i
//six conditions is in consideration
int cnt = ;
if(A.r < B.r) { swap(A, B); swap(a, b); }
int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
int rdiff = A.r - B.r;
int rsum = A.r + B.r;
if(d2 < rdiff * rdiff) return ; // one circle is inside the other
double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
if(d2 == && A.r == B.r) return -; // two circle duplicates
if(d2 == rdiff * rdiff){ // internal tangency
a[cnt] = A.point(base); b[cnt] = B.point(base); cnt++;
return ;
}
double ang = acos((A.r - B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang);
if(d2 == rsum * rsum){
//one internal tangent
a[cnt] = A.point(base);
b[cnt++] = B.point(base + PI);
}else if(d2 > rsum * rsum){
//two internal tangents
double ang = acos((A.r + B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang + PI);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang + PI);
}
return cnt;
}
Point ReadPoint(){
double x, y;
scanf("%lf%lf", &x, &y);
return Point(x, y);
}
Circle ReadCircle(){
double x, y, r;
scanf("%lf%lf%lf", &x, &y, &r);
return Circle(x, y, r);
}
//Here goes 3d geometry templates
struct Point3{
double x, y, z;
Point3(double x = , double y = , double z = ) : x(x), y(y), z(z) {}
};
typedef Point3 Vector3;
Vector3 operator + (Vector3 A, Vector3 B){
return Vector3(A.x + B.x, A.y + B.y, A.z + B.z);
}
Vector3 operator - (Vector3 A, Vector3 B){
return Vector3(A.x - B.x, A.y - B.y, A.z - B.z);
}
Vector3 operator * (Vector3 A, double p){
return Vector3(A.x * p, A.y * p, A.z * p);
}
Vector3 operator / (Vector3 A, double p){
return Vector3(A.x / p, A.y / p, A.z / p);
}
double Dot3(Vector3 A, Vector3 B){
return A.x * B.x + A.y * B.y + A.z * B.z;
}
double Len3(Vector3 A){
return sqrt(Dot3(A, A));
}
double Angle3(Vector3 A, Vector3 B){
return acos(Dot3(A, B) / Len3(A) / Len3(B));
}
double DistanceToPlane(const Point3& p, const Point3 &p0, const Vector3& n){
return abs(Dot3(p - p0, n));
}
Point3 GetPlaneProjection(const Point3 &p, const Point3 &p0, const Vector3 &n){
return p - n * Dot3(p - p0, n);
}
Point3 GetLinePlaneIntersection(Point3 p1, Point3 p2, Point3 p0, Vector3 n){
Vector3 v = p2 - p1;
double t = (Dot3(n, p0 - p1) / Dot3(n, p2 - p1));
return p1 + v * t;//if t in range [0, 1], intersection on segment
}
Vector3 Cross(Vector3 A, Vector3 B){
return Vector3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}
double Area3(Point3 A, Point3 B, Point3 C){
return Len3(Cross(B - A, C - A));
}
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
}
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
int mod;
//-------------------------------------------------------------------------
const int maxn = 1e2 + ;
ll D, H, B, L;
double _ratio;
double P(double x){
return x * sqrt( + x * x) + log(sqrt( + x * x) + x);
}
double Q(double x){
return _ratio * x;
}
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int T = readint(), kase = ;
while(T--){
scanf("%lld%lld%lld%lld", &D, &H, &B, &L);
double cnt = (double)B / D;
ll m = (ll)cnt;
maximize(m, );
while(B > m * D) ++m;
_ratio = (double)L / B * ;
double l = , r = 1e60;
while(r - l > 1e-){
double mid = l + (r - l) / ;
double p0 = P(mid), q0 = Q(mid);
if(p0 > q0) r = mid;
else l = mid;
}
double ans = l;
//dbg2("ratio", _ratio);
//dbg2("ans", ans);
printf("Case %d:\n", ++kase);
printf("%.2f\n", H - ((double)B * ans) / . / (double)m);
if(T) putchar('\n');
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
17.Uva 11752 The Super Powers
关键词：STL
提示：注意数值转化和溢出
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define PI acos(-1.)
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
#define low_bit(x) ((x) & (-x))
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
inline int readint(){
int x;
scanf("%d", &x);
return x;
}
inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
}
//Here goes 2d geometry templates
struct Point{
double x, y;
Point(double x = , double y = ) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){
return Vector(A.x + B.x, A.y + B.y);
}
Vector operator - (Point A, Point B){
return Vector(A.x - B.x, A.y - B.y);
}
Vector operator * (Vector A, double p){
return Vector(A.x * p, A.y * p);
}
Vector operator / (Vector A, double p){
return Vector(A.x / p, A.y / p);
}
bool operator < (const Point& a, const Point& b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int dcmp(double x){
if(abs(x) < eps) return ;
return x < ? - : ;
}
bool operator == (const Point& a, const Point& b){
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
}
double Dot(Vector A, Vector B){
return A.x * B.x + A.y * B.y;
}
double Len(Vector A){
return sqrt(Dot(A, A));
}
double Angle(Vector A, Vector B){
return acos(Dot(A, B) / Len(A) / Len(B));
}
double Cross(Vector A, Vector B){
return A.x * B.y - A.y * B.x;
}
double Area2(Point A, Point B, Point C){
return Cross(B - A, C - A);
}
Vector Rotate(Vector A, double rad){
//rotate counterclockwise
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
Vector Normal(Vector A){
double L = Len(A);
return Vector(-A.y / L, A.x / L);
}
void Normallize(Vector &A){
double L = Len(A);
A.x /= L, A.y /= L;
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
double DistanceToLine(Point P, Point A, Point B){
Vector v1 = B - A, v2 = P - A;
return abs(Cross(v1, v2)) / Len(v1);
}
double DistanceToSegment(Point P, Point A, Point B){
if(A == B) return Len(P - A);
Vector v1 = B - A, v2 = P - A, v3 = P - B;
if(dcmp(Dot(v1, v2)) < ) return Len(v2);
else if(dcmp(Dot(v1, v3)) > ) return Len(v3);
else return abs(Cross(v1, v2)) / Len(v1);
}
Point GetLineProjection(Point P, Point A, Point B){
Vector v = B - A;
return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2){
//Line1:(a1, a2) Line2:(b1,b2)
double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
}
bool OnSegment(Point p, Point a1, Point a2){
return dcmp(Cross(a1 - p, a2 - p)) == && dcmp(Dot(a1 - p, a2 -p)) < ;
}
Vector GetBisector(Vector v, Vector w){
Normallize(v), Normallize(w);
return Vector((v.x + w.x) / , (v.y + w.y) / );
} bool OnLine(Point p, Point a1, Point a2){
Vector v1 = p - a1, v2 = a2 - a1;
double tem = Cross(v1, v2);
return dcmp(tem) == ;
}
struct Line{
Point p;
Vector v;
Point point(double t){
return Point(p.x + t * v.x, p.y + t * v.y);
}
Line(Point p, Vector v) : p(p), v(v) {}
};
struct Circle{
Point c;
double r;
Circle(Point c, double r) : c(c), r(r) {}
Circle(int x, int y, int _r){
c = Point(x, y);
r = _r;
}
Point point(double a){
return Point(c.x + cos(a) * r, c.y + sin(a) * r);
}
};
int GetLineCircleIntersection(Line L, Circle C, double &t1, double& t2, vector<Point>& sol){
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
double e = a * a + c * c, f = * (a * b + c * d), g = b * b + d * d - C.r * C.r;
double delta = f * f - * e * g;
if(dcmp(delta) < ) return ;
if(dcmp(delta) == ){
t1 = t2 = -f / ( * e); sol.pb(L.point(t1));
return ;
}
t1 = (-f - sqrt(delta)) / ( * e); sol.pb(L.point(t1));
t2 = (-f + sqrt(delta)) / ( * e); sol.pb(L.point(t2));
return ;
}
double angle(Vector v){
return atan2(v.y, v.x);
//(-pi, pi]
}
int GetCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol){
double d = Len(C1.c - C2.c);
if(dcmp(d) == ){
if(dcmp(C1.r - C2.r) == ) return -; //two circle duplicates
return ; //two circles share identical center
}
if(dcmp(C1.r + C2.r - d) < ) return ; //too close
if(dcmp(abs(C1.r - C2.r) - d) > ) return ; //too far away
double a = angle(C2.c - C1.c); // angle of vector(C1, C2)
double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / ( * C1.r * d));
Point p1 = C1.point(a - da), p2 = C1.point(a + da);
sol.pb(p1);
if(p1 == p2) return ;
sol.pb(p2);
return ;
}
int GetPointCircleTangents(Point p, Circle C, Vector* v){
Vector u = C.c - p;
double dist = Len(u);
if(dist < C.r) return ;//p is inside the circle, no tangents
else if(dcmp(dist - C.r) == ){
// p is on the circles, one tangent only
v[] = Rotate(u, PI / );
return ;
}else{
double ang = asin(C.r / dist);
v[] = Rotate(u, -ang);
v[] = Rotate(u, +ang);
return ;
}
}
int GetCircleCircleTangents(Circle A, Circle B, Point* a, Point* b){
//a[i] store point of tangency on Circle A of tangent i
//b[i] store point of tangency on Circle B of tangent i
//six conditions is in consideration
int cnt = ;
if(A.r < B.r) { swap(A, B); swap(a, b); }
int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
int rdiff = A.r - B.r;
int rsum = A.r + B.r;
if(d2 < rdiff * rdiff) return ; // one circle is inside the other
double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
if(d2 == && A.r == B.r) return -; // two circle duplicates
if(d2 == rdiff * rdiff){ // internal tangency
a[cnt] = A.point(base); b[cnt] = B.point(base); cnt++;
return ;
}
double ang = acos((A.r - B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang);
if(d2 == rsum * rsum){
//one internal tangent
a[cnt] = A.point(base);
b[cnt++] = B.point(base + PI);
}else if(d2 > rsum * rsum){
//two internal tangents
double ang = acos((A.r + B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang + PI);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang + PI);
}
return cnt;
}
Point ReadPoint(){
double x, y;
scanf("%lf%lf", &x, &y);
return Point(x, y);
}
Circle ReadCircle(){
double x, y, r;
scanf("%lf%lf%lf", &x, &y, &r);
return Circle(x, y, r);
}
//Here goes 3d geometry templates
struct Point3{
double x, y, z;
Point3(double x = , double y = , double z = ) : x(x), y(y), z(z) {}
};
typedef Point3 Vector3;
Vector3 operator + (Vector3 A, Vector3 B){
return Vector3(A.x + B.x, A.y + B.y, A.z + B.z);
}
Vector3 operator - (Vector3 A, Vector3 B){
return Vector3(A.x - B.x, A.y - B.y, A.z - B.z);
}
Vector3 operator * (Vector3 A, double p){
return Vector3(A.x * p, A.y * p, A.z * p);
}
Vector3 operator / (Vector3 A, double p){
return Vector3(A.x / p, A.y / p, A.z / p);
}
double Dot3(Vector3 A, Vector3 B){
return A.x * B.x + A.y * B.y + A.z * B.z;
}
double Len3(Vector3 A){
return sqrt(Dot3(A, A));
}
double Angle3(Vector3 A, Vector3 B){
return acos(Dot3(A, B) / Len3(A) / Len3(B));
}
double DistanceToPlane(const Point3& p, const Point3 &p0, const Vector3& n){
return abs(Dot3(p - p0, n));
}
Point3 GetPlaneProjection(const Point3 &p, const Point3 &p0, const Vector3 &n){
return p - n * Dot3(p - p0, n);
}
Point3 GetLinePlaneIntersection(Point3 p1, Point3 p2, Point3 p0, Vector3 n){
Vector3 v = p2 - p1;
double t = (Dot3(n, p0 - p1) / Dot3(n, p2 - p1));
return p1 + v * t;//if t in range [0, 1], intersection on segment
}
Vector3 Cross(Vector3 A, Vector3 B){
return Vector3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}
double Area3(Point3 A, Point3 B, Point3 C){
return Len3(Cross(B - A, C - A));
}
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
}
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {-, , , };
int dy[] = {, , -, };
const int mod = 1e9 + ;
//-------------------------------------------------------------------------
const int maxn = 1e6 + ;
const double limit = (double)(1ll << ) * . - .;
int k;
int prime[ << ], pointer;
bool vis[( << ) + ];
ul power(ul tem, int times){
ul ans = .;
while(times){
if(times & ) ans *= tem;
times >>= ;
tem *= tem;
}
return ans;
}
bool is_prime(int x){
if(x == ) return ;
if(!(x & )) return ;
int mid = (int)sqrt(x);
for(int i = ; i <= mid; i += ){
if(x % i == ) return ;
}
return ;
}
//------------------------------------------------------------------------- int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("in.txt", "w", stdout);
set<ul> S;
S.clear();
for(int i = ; i < ; i++){
if(is_prime(i)) continue;
double lim = exp(. / i * log());
for(int j = ; j < lim; j++){
ul tem = power(j, i);
S.insert(tem);
}
}
S.insert();
//dbg(S.size());
set<ul> :: iterator it;
it = S.begin();
while(it != S.end()){
printf("%llu\n", *it);
++it;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
18.LA 4060 The Bells are Ringing
关键词：随机素数分解算法，暴力
提示：可能存在别的解法？
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <iostream>
#include <assert.h>
#define PI acos(-1.)
#pragma comment(linker, "/STACK:102400000,102400000")
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define st first
#define nd second
#define keyn (root->ch[1]->ch[0])
#define lson (u << 1)
#define rson (u << 1 | 1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define type(x) __typeof(x.begin())
#define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
#define FOR(i, s, t) for(int i = (s); i <= (t); i++)
#define ROF(i, t, s) for(int i = (t); i >= (s); i--)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << " " << y << endl
#define clr(x, i) memset(x, (i), sizeof(x))
#define maximize(x, y) x = max((x), (y))
#define minimize(x, y) x = min((x), (y))
using namespace std;
typedef long long ll;
const int int_inf = 0x3f3f3f3f;
const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
const int INT_INF = (int)((1ll << ) - );
const double double_inf = 1e30;
const double eps = 1e-;
typedef unsigned long long ul;
inline int readint(){
int x;
scanf("%d", &x);
return x;
}
inline int readstr(char *s){
scanf("%s", s);
return strlen(s);
}
//Here goes 2d geometry templates
struct Point{
double x, y;
Point(double x = , double y = ) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){
return Vector(A.x + B.x, A.y + B.y);
}
Vector operator - (Point A, Point B){
return Vector(A.x - B.x, A.y - B.y);
}
Vector operator * (Vector A, double p){
return Vector(A.x * p, A.y * p);
}
Vector operator / (Vector A, double p){
return Vector(A.x / p, A.y / p);
}
bool operator < (const Point& a, const Point& b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
int dcmp(double x){
if(abs(x) < eps) return ;
return x < ? - : ;
}
bool operator == (const Point& a, const Point& b){
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
}
double Dot(Vector A, Vector B){
return A.x * B.x + A.y * B.y;
}
double Len(Vector A){
return sqrt(Dot(A, A));
}
double Angle(Vector A, Vector B){
return acos(Dot(A, B) / Len(A) / Len(B));
}
double Cross(Vector A, Vector B){
return A.x * B.y - A.y * B.x;
}
double Area2(Point A, Point B, Point C){
return Cross(B - A, C - A);
}
Vector Rotate(Vector A, double rad){
//rotate counterclockwise
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
Vector Normal(Vector A){
double L = Len(A);
return Vector(-A.y / L, A.x / L);
}
void Normallize(Vector &A){
double L = Len(A);
A.x /= L, A.y /= L;
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){
Vector u = P - Q;
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
double DistanceToLine(Point P, Point A, Point B){
Vector v1 = B - A, v2 = P - A;
return abs(Cross(v1, v2)) / Len(v1);
}
double DistanceToSegment(Point P, Point A, Point B){
if(A == B) return Len(P - A);
Vector v1 = B - A, v2 = P - A, v3 = P - B;
if(dcmp(Dot(v1, v2)) < ) return Len(v2);
else if(dcmp(Dot(v1, v3)) > ) return Len(v3);
else return abs(Cross(v1, v2)) / Len(v1);
}
Point GetLineProjection(Point P, Point A, Point B){
Vector v = B - A;
return A + v * (Dot(v, P - A) / Dot(v, v));
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2){
//Line1:(a1, a2) Line2:(b1,b2)
double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
}
bool OnSegment(Point p, Point a1, Point a2){
return dcmp(Cross(a1 - p, a2 - p)) == && dcmp(Dot(a1 - p, a2 -p)) < ;
}
Vector GetBisector(Vector v, Vector w){
Normallize(v), Normallize(w);
return Vector((v.x + w.x) / , (v.y + w.y) / );
} bool OnLine(Point p, Point a1, Point a2){
Vector v1 = p - a1, v2 = a2 - a1;
double tem = Cross(v1, v2);
return dcmp(tem) == ;
}
struct Line{
Point p;
Vector v;
Point point(double t){
return Point(p.x + t * v.x, p.y + t * v.y);
}
Line(Point p, Vector v) : p(p), v(v) {}
};
struct Circle{
Point c;
double r;
Circle(Point c, double r) : c(c), r(r) {}
Circle(int x, int y, int _r){
c = Point(x, y);
r = _r;
}
Point point(double a){
return Point(c.x + cos(a) * r, c.y + sin(a) * r);
}
};
int GetLineCircleIntersection(Line L, Circle C, double &t1, double& t2, vector<Point>& sol){
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
double e = a * a + c * c, f = * (a * b + c * d), g = b * b + d * d - C.r * C.r;
double delta = f * f - * e * g;
if(dcmp(delta) < ) return ;
if(dcmp(delta) == ){
t1 = t2 = -f / ( * e); sol.pb(L.point(t1));
return ;
}
t1 = (-f - sqrt(delta)) / ( * e); sol.pb(L.point(t1));
t2 = (-f + sqrt(delta)) / ( * e); sol.pb(L.point(t2));
return ;
}
double angle(Vector v){
return atan2(v.y, v.x);
//(-pi, pi]
}
int GetCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol){
double d = Len(C1.c - C2.c);
if(dcmp(d) == ){
if(dcmp(C1.r - C2.r) == ) return -; //two circle duplicates
return ; //two circles share identical center
}
if(dcmp(C1.r + C2.r - d) < ) return ; //too close
if(dcmp(abs(C1.r - C2.r) - d) > ) return ; //too far away
double a = angle(C2.c - C1.c); // angle of vector(C1, C2)
double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / ( * C1.r * d));
Point p1 = C1.point(a - da), p2 = C1.point(a + da);
sol.pb(p1);
if(p1 == p2) return ;
sol.pb(p2);
return ;
}
int GetPointCircleTangents(Point p, Circle C, Vector* v){
Vector u = C.c - p;
double dist = Len(u);
if(dist < C.r) return ;//p is inside the circle, no tangents
else if(dcmp(dist - C.r) == ){
// p is on the circles, one tangent only
v[] = Rotate(u, PI / );
return ;
}else{
double ang = asin(C.r / dist);
v[] = Rotate(u, -ang);
v[] = Rotate(u, +ang);
return ;
}
}
int GetCircleCircleTangents(Circle A, Circle B, Point* a, Point* b){
//a[i] store point of tangency on Circle A of tangent i
//b[i] store point of tangency on Circle B of tangent i
//six conditions is in consideration
int cnt = ;
if(A.r < B.r) { swap(A, B); swap(a, b); }
int d2 = (A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y);
int rdiff = A.r - B.r;
int rsum = A.r + B.r;
if(d2 < rdiff * rdiff) return ; // one circle is inside the other
double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);
if(d2 == && A.r == B.r) return -; // two circle duplicates
if(d2 == rdiff * rdiff){ // internal tangency
a[cnt] = A.point(base); b[cnt] = B.point(base); cnt++;
return ;
}
double ang = acos((A.r - B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang);
if(d2 == rsum * rsum){
//one internal tangent
a[cnt] = A.point(base);
b[cnt++] = B.point(base + PI);
}else if(d2 > rsum * rsum){
//two internal tangents
double ang = acos((A.r + B.r) / sqrt(d2));
a[cnt] = A.point(base + ang); b[cnt++] = B.point(base + ang + PI);
a[cnt] = A.point(base - ang); b[cnt++] = B.point(base - ang + PI);
}
return cnt;
}
Point ReadPoint(){
double x, y;
scanf("%lf%lf", &x, &y);
return Point(x, y);
}
Circle ReadCircle(){
double x, y, r;
scanf("%lf%lf%lf", &x, &y, &r);
return Circle(x, y, r);
}
//Here goes 3d geometry templates
struct Point3{
double x, y, z;
Point3(double x = , double y = , double z = ) : x(x), y(y), z(z) {}
};
typedef Point3 Vector3;
Vector3 operator + (Vector3 A, Vector3 B){
return Vector3(A.x + B.x, A.y + B.y, A.z + B.z);
}
Vector3 operator - (Vector3 A, Vector3 B){
return Vector3(A.x - B.x, A.y - B.y, A.z - B.z);
}
Vector3 operator * (Vector3 A, double p){
return Vector3(A.x * p, A.y * p, A.z * p);
}
Vector3 operator / (Vector3 A, double p){
return Vector3(A.x / p, A.y / p, A.z / p);
}
double Dot3(Vector3 A, Vector3 B){
return A.x * B.x + A.y * B.y + A.z * B.z;
}
double Len3(Vector3 A){
return sqrt(Dot3(A, A));
}
double Angle3(Vector3 A, Vector3 B){
return acos(Dot3(A, B) / Len3(A) / Len3(B));
}
double DistanceToPlane(const Point3& p, const Point3 &p0, const Vector3& n){
return abs(Dot3(p - p0, n));
}
Point3 GetPlaneProjection(const Point3 &p, const Point3 &p0, const Vector3 &n){
return p - n * Dot3(p - p0, n);
}
Point3 GetLinePlaneIntersection(Point3 p1, Point3 p2, Point3 p0, Vector3 n){
Vector3 v = p2 - p1;
double t = (Dot3(n, p0 - p1) / Dot3(n, p2 - p1));
return p1 + v * t;//if t in range [0, 1], intersection on segment
}
Vector3 Cross(Vector3 A, Vector3 B){
return Vector3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z, A.x * B.y - A.y * B.x);
}
double Area3(Point3 A, Point3 B, Point3 C){
return Len3(Cross(B - A, C - A));
}
class cmpt{
public:
bool operator () (const int &x, const int &y) const{
return x > y;
}
}; int Rand(int x, int o){
//if o set, return [1, x], else return [0, x - 1]
if(!x) return ;
int tem = (int)((double)rand() / RAND_MAX * x) % x;
return o ? tem + : tem;
}
////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
void data_gen(){
srand(time());
freopen("in.txt", "w", stdout);
int times = ;
printf("%d\n", times);
while(times--){
int r = Rand(, ), a = Rand(, ), c = Rand(, );
int b = Rand(r, ), d = Rand(r, );
int m = Rand(, ), n = Rand(m, );
printf("%d %d %d %d %d %d %d\n", n, m, a, b, c, d, r);
}
} struct cmpx{
bool operator () (int x, int y) { return x > y; }
};
int debug = ;
int dx[] = {, , , };
int dy[] = {, , , };
//-------------------------------------------------------------------------
const int maxn = 1e5 + ;
ll fac[maxn];
int pointer;
ll p[];
int k;
int cnt[];
pair<ll, pll> ans[maxn];
int pt;
ll n;
int S = ; ll multi(ll a, ll b, ll c){
a %= c, b %= c;
ll res = ;
while(b){
if(b & ) res += a, res %= c;
a <<= ;
if(a >= c) a %= c;
b >>= ;
}
return res;
}
ll power(ll x, ll n, ll mod){
if(n == ) return x % mod;
x %= mod;
ll tmp = x;
ll res = ;
while(n){
if(n & ) res = multi(res, tmp, mod);
tmp = multi(tmp, tmp, mod);
n >>= ;
}
return res;
}
bool check(ll a, ll n, ll x, ll t){
ll res = power(a, x, n);
ll last = res;
FOR(i, , t){
res = multi(res, res, n);
if(res == && last != && last != n - ) return ;
last = res;
}
if(res != ) return ;
return ;
}
bool miller_rabin(ll n){
if(n < ) return ;
if(n == ) return ;
if((n & ) == ) return ;
ll x = n - ;
ll t = ;
while((x & ) == ) x >>= , ++t;
FOR(i, , S - ){
ll a = rand() % (n - ) + ;
if(check(a, n, x, t)) return ;
}
return ;
}
ll gcd(ll a, ll b){
if(a == ) return ;
if(a < ) return gcd(-a, b);
while(b){
ll t = a % b;
a = b;
b = t;
}
return a;
}
ll pollard_rho(ll x, ll c){
ll i = , k = ;
ll x0 = rand() % x;
ll y = x0;
while(true){
++i;
x0 = (multi(x0, x0, x) + c) % x;
ll d = gcd(y - x0, x);
if(d != && d != x) return d;
if(y == x0) return x;
if(i == k){
y = x0;
k += k;
}
}
}
void factorize(ll n){
if(miller_rabin(n)){
p[k++] = n;
return;
}
ll p = n;
while(p >= n) p = pollard_rho(p, rand() % (n - ) + );
factorize(p);
factorize(n / p);
}
void dfs(int pos, ll cur){
if(pos == k){
fac[pointer++] = cur;
return;
}
ll tem = ;
FOR(i, , cnt[pos]){
dfs(pos + , cur * tem);
tem *= p[pos];
}
}
void solve(){
srand(time());
pointer = k = pt = ;
factorize(n);
//FOR(i, 0, k - 1) printf("%lld\n", p[i]);
sort(p, p + k);
k = unique(p, p + k) - p;
ll tem = n;
clr(cnt, );
FOR(i, , k - ) while(tem % p[i] == ) ++cnt[i], tem /= p[i];
dfs(, );
sort(fac, fac + pointer);
FOR(i, , pointer - ){
int rear = i + ;
while(rear < pointer && fac[rear] - fac[i] <= ) ++rear;
FOR(j, i + , rear - ) FOR(u, j + , rear - ){
if(fac[u] > 1e6) continue;
ll tem = fac[i] / gcd(fac[i], fac[j]) * fac[j];
tem = tem / gcd(tem, fac[u]) * fac[u];
if(tem == n) ans[pt++] = mp(fac[i], mp(fac[j], fac[u]));
}
}
}
//-------------------------------------------------------------------------
int main(){
//data_gen(); return 0;
//C(); return 0;
debug = ;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
if(debug) freopen("in.txt", "r", stdin);
//freopen("in.txt", "w", stdout);
int kase = ;
while(~scanf("%lld", &n) && n){
solve();
printf("Scenario %d:\n", ++kase);
if(!pt) puts("Such bells don't exist");
else FOR(i, , pt - ) printf("%lld %lld %lld\n", ans[i].st, ans[i].nd.st, ans[i].nd.nd);
puts("");
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
return ;
}
code：
