题目链接：http://acm.hdu.edu.cn/search.php?field=problem&key=2016ACM%2FICPC%D1%C7%D6%DE%C7%F8%B4%F3%C1%AC%D5%BE-%D6%D8%CF%D6%C8%FC%A3%A8%B8%D0%D0%BB%B4%F3%C1%AC%BA%A3%CA%C2%B4%F3%D1%A7%A3%A9&source=1&searchmode=source
A.染色乱搞。
#include <bits/stdc++.h>
using namespace std; typedef struct Edge {
int to, next;
}Edge; const int maxn = ;
int n, m, x, y;
int know[maxn], vis[maxn], color[maxn];
int ecnt, head[maxn];
Edge e[maxn*maxn]; void init() {
ecnt = ;
memset(head, -, sizeof(head));
memset(know, , sizeof(know));
memset(vis, , sizeof(vis));
memset(color, , sizeof(color));
} void adde(int u, int v) {
e[ecnt].to = v, e[ecnt].next = head[u];
head[u] = ecnt++;
} bool dfs(int u) {
for(int i = head[u]; ~i; i=e[i].next) {
int v = e[i].to;
if(color[v] == color[u]) return ;
if(vis[v]) continue;
vis[v] = ;
color[v] = - color[u];
if(!dfs(v)) return ;
}
return ;
} int main() {
// freopen("in", "r", stdin);
int u, v;
while(~scanf("%d%d%d%d",&n,&m,&x,&y)) {
init();
for(int i = ; i < m; i++) {
scanf("%d%d",&u,&v);
adde(u, v); adde(v, u);
know[u] = know[v] = ;
}
for(int i = ; i < x; i++) {
scanf("%d", &u);
color[u] = ; know[u] = ;
}
for(int i = ; i < y; i++) {
scanf("%d", &u);
color[u] = ; know[u] = ;
}
bool flag = ;
for(int i = ; i <= n; i++) {
if(!know[i]) {
flag = ;
break;
}
}
if(flag) {
puts("NO");
continue;
}
for(int i = ; i <= n; i++) {
if(color[i]) {
vis[i] = ;
if(!dfs(i)) {
flag = ;
break;
}
}
}
for(int i = ; i <= n; i++) {
if(!color[i]) {
vis[i] = ;
color[i] = ;
if(!dfs(i)) {
flag = ;
break;
}
}
}
if(!flag) puts("YES");
else puts("NO");
}
return ;
}
A
C.威佐夫博弈+大数，根号5用mathmatica跑出来的，其实可以用二分打表。
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.Scanner; public class Main { public static void main(String[] args) {
Scanner in = new Scanner(System.in);
BigDecimal n, m;
BigDecimal sqrt5 = new BigDecimal("2.2360679774997896964091736687312762354406183596115257242708972454105209256378048994144144083787822749695081761507737835");
while(in.hasNextBigDecimal()) {
n = in.nextBigDecimal(); m = in.nextBigDecimal();
if(m.equals(n.max(m))) {
BigDecimal x = n;
n = m;
m = x;
}
BigDecimal k = n.subtract(m);
BigDecimal p = new BigDecimal(1);
n = p.add(sqrt5).multiply(k);
n = n.divide(new BigDecimal(2));
if(n.toBigInteger().equals(m.toBigInteger())) System.out.println("0");
else System.out.println("1");
}
}
}
C
二分打sqrt(5)
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.Scanner; public class Main {
public static BigDecimal Get(BigDecimal x) {
BigDecimal lo = new BigDecimal("0.000000000000000000000000000001");
BigDecimal hi = x;
for(int i = 0; i < 1000; i++) {
BigDecimal mid = lo.add(hi).divide(new BigDecimal("2.0"));
BigDecimal mid2 = mid.multiply(mid);
if(mid2.max(x).equals(mid2)) hi = mid;
else lo = mid;
}
return hi;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
BigDecimal n, m;
BigDecimal sqrt5 = Get(new BigDecimal(5));
while(in.hasNextBigDecimal()) {
n = in.nextBigDecimal(); m = in.nextBigDecimal();
if(m.equals(n.max(m))) {
BigDecimal x = n;
n = m;
m = x;
}
BigDecimal k = n.subtract(m);
BigDecimal p = new BigDecimal(1);
n = p.add(sqrt5).multiply(k);
n = n.divide(new BigDecimal(2));
if(n.toBigInteger().equals(m.toBigInteger())) System.out.println("0");
else System.out.println("1");
}
}
}
C
D.找到规律gcd(a,b)=gcd(x,y)以后，就是解方程了。
#include <bits/stdc++.h>
using namespace std; typedef long long LL;
LL a, b, x, y; LL gcd(LL x, LL y) {
return y == ? x : gcd(y, x % y);
}
int main() {
// freopen("in", "r", stdin);
while(~scanf("%I64d%I64d",&a,&b)) {
LL g = gcd(a, b);
LL k = b * g;
if(a * a - * k < || (LL)sqrt(a*a-*k) != sqrt(a*a-*k)) puts("No Solution");
else {
LL delta = (LL)sqrt(a * a - * k);
printf("%I64d %I64d\n", (a-delta)/, (a+delta)/);
}
}
return ;
}
D
F.考虑让整个数列a最长，那么就是公差为1的等差数列，这时候一定会有不够或者超过x的情况。这时候就把多余的部分从后往前+1补齐。问题就变成在这样一个数列里找到最长的不大于x的个数。由于有取模，所以除法用逆元来做。
#include <bits/stdc++.h>
using namespace std; typedef long long LL; LL exgcd(LL a, LL b, LL &x, LL &y) {
if(b == ) {
x = ;
y = ;
return a;
}
else {
LL ret = exgcd(b, a%b, x, y);
LL tmp = x;
x = y;
y = tmp - a / b * y;
return ret;
}
} LL inv(LL a, LL m) {
LL x, y;
exgcd(a, m, x, y);
return (x % m + m) % m;
} const LL mod = (LL)1e9+;
const int maxn = ;
LL f[maxn];
int x; void init() {
memset(f, , sizeof(f));
f[] = ; f[] = ;
for(int i = ; i < maxn; i++) {
f[i] = (f[i-] * i) % mod;
}
} int main() {
// freopen("in", "r", stdin);
init();
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &x);
if(x <= ) {
printf("%d\n", x);
continue;
}
int lo = , hi = maxn;
int pos = ;
while(lo <= hi) {
int mid = (lo + hi) >> ;
LL s = (mid + ) * (mid - ) / ;
if(s <= x) {
lo = mid + ;
pos = max(pos, mid);
}
else hi = mid - ;
}
x -= (pos + ) * (pos - ) / ;
if(x == pos) printf("%I64d\n", (f[pos]*inv(,mod))%mod*(pos+)%mod);
else if(pos == ) printf("%I64d\n", f[pos]);
else printf("%I64d\n", f[pos+]*inv(pos-x+,mod)%mod);
}
return ;
}
F
H.奇数就无所谓，偶数的话先手有优势。
#include <bits/stdc++.h>
using namespace std; int k; int main() {
// freopen("in", "r", stdin);
while(~scanf("%d", &k)) {
if(k & ) puts("");
else puts("");
}
return ;
}
H
I.余弦定理求出第三条边，高用角的一半的余弦乘一下斜边，面积加起来。
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
const double pi = 3.141592653;
int n, d;
int th;
double ret; double f(int th) {
return d*cos(pi*th/2.0/180.0)*sqrt(2.0*d*d-2.0*d*d*cos(pi*th/180.0))/2.0;
} int main() {
// freopen("in", "r", stdin);
while(~scanf("%d%d",&n,&d)) {
ret = 0.0;
for(int i = ; i <= n; i++) {
scanf("%d", &th);
ret += f(th);
}
printf("%.3lf\n", ret);
}
return ;
}
I
J.拆成四部分挨个看看是不是97。
#include <bits/stdc++.h>
using namespace std; const int maxn = ;
int n;
int a; int f(int x) {
int cnt = ;
int q = ;
while(q--) {
if((x % ) == ) cnt++;
x >>= ;
}
return cnt;
} int main() {
// freopen("in", "r", stdin);
while(~scanf("%d", &n)) {
int ret = ;
for(int i = ; i <= n; i++) {
scanf("%d", &a);
ret += f(a);
}
printf("%d\n", ret);
}
return ;
}
J