2018 ICPC南京现场赛
A Adrien and Austin
题目链接
题意：有n块石头，下标从1-n。每个人能够拿[1,k]个数量的连续块。两个人轮流拿，若一个人不能拿则失败。求谁胜利。
思路：先手必败态1、n=0 2、n=1并且n%2==0。当k>=2时，先手可以先拿中间部分，无论后手怎么拿，先手在零一半的地方复制即可保持胜利。
#include <bits/stdc++.h>
using namespace std;
string a="Adrien";
string b="Austin";
int main(){
int n,k;
scanf("%d%d",&n,&k);
if(n==0)
cout<<b<<endl;
else if(k>=2)
cout<<a<<endl;
else if(n%2==1)
cout<<a<<endl;
else
cout<<b<<endl;
return 0;
} D Prime Game
题目链接
题意：未知。
思路：模拟退火。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <math.h>
#include <cstdlib>
#include <algorithm>
#define sqr(x) ((x)*(x))
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
#define maxn 106
#define eps 1e-8
using namespace std;
struct cpoint {
double x, y, z, d;
};
cpoint cp[maxn], rp;
int n;
double dis(cpoint p, cpoint q) {
return sqrt(sqr(p.x - q.x) + sqr(p.y - q.y) + sqr(p.z - q.z));
}
const int N = 2e5;
void solve() {
int L = 300, id, ip;
rp.x = double((rand() % 1000000 + 1) / 1000000.00000 * N);
rp.y = double((rand() % 1000000 + 1) / 1000000.00000 * N);
rp.z = double((rand() % 1000000 + 1) / 1000000.00000 * N);
rp.d = 0.0;
for (int i = 0; i<n; i++) {
if (dis(rp, cp[i])>rp.d) {
rp.d = dis(rp, cp[i]);
id = i;
}
}
double dal = 100;
while (dal>eps) {
for (int i = 0; i<L; i++) {
rp.x += dal * (cp[id].x - rp.x) / rp.d;
rp.y += dal * (cp[id].y - rp.y) / rp.d;
rp.z += dal * (cp[id].z - rp.z) / rp.d;
rp.d = 0.0;
for (int j = 0; j<n; j++)
if (dis(rp, cp[j])>rp.d) {
id = j;
rp.d = dis(rp, cp[j]);
}
}
dal *= 0.98;
}
printf("%.15lf\n", rp.d);
}
int main() {
while (scanf("%d", &n) != EOF) {
if (n == 0)break;
for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf", &cp[i].x, &cp[i].y, &cp[i].z);
cp[i].x += 1e5;
cp[i].y += 1e5;
cp[i].z += 1e5;
}
solve();
}
}
/*
4
0 0 0
10000 0 0
0 10000 0
0 0 10000
3
0 0 0
3 0 0
0 4 0
*/
/*
8164.96631812619
8164.965809282082773 95
8164.965809399971477 93
8164.966205792577966 94
*/E Eva and Euro coins
题目链接
题意：给你01字符串s和t，要求s和t最终相同，只有一种操作选择连续k个相同面的硬币翻转。
思路：用栈维护连续的硬币，贪心消去
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#include<cstdlib>
#include<ctime>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
char ch1[maxn * 10], ch2[maxn * 10];
vector<int> v1, v2, num;
int main(void){
int n, k, i, j, flag, s;
scanf("%d %d",&n,&k);
scanf("%s %s",ch1,ch2);
if(k > 1){
flag = ch1[0];
num.push_back(1);
v1.push_back(ch1[0]);
s = 1;
for(i = 1;i < n;i++){
v1.push_back(ch1[i]);
if(ch1[i] == flag){
num[s - 1]++;
if(num[s - 1] == k){
for(j = 0;j < k;j++){
v1.pop_back();
}
num.pop_back();
s--;
if(v1.empty()){
flag = 0;
}
else{
flag = '0' + '1' - flag;
}
}
}
else{
flag = ch1[i];
num.push_back(1);
s++;
}
}
num.clear();
flag = ch2[0];
num.push_back(1);
v2.push_back(ch2[0]);
s = 1;
for(i = 1;i < n;i++){
v2.push_back(ch2[i]);
if(ch2[i] == flag){
num[s - 1]++;
if(num[s - 1] == k){
for(j = 0;j < k;j++){
v2.pop_back();
}
num.pop_back();
s--;
if(v2.empty()){
flag = 0;
}
else{
flag = '0' + '1' - flag;
}
}
}
else{
flag = ch2[i];
num.push_back(1);
s++;
}
}
flag = 1;
s = v1.size();
if(s == v2.size()){
for(i = 0;i < s;i++){
if(v1[i] != v2[i]){
flag = 0;
break;
}
}
}
else{
flag = 0;
}
if(flag){
puts("Yes");
}
else{
puts("No");
}
}
else{
puts("Yes");
}
return 0;
}G Pyramid
题目链接
题意：由n*(n-1)/2个黑三角形组成大的三角形。求这些黑三角形的顶点选三个可以组成三角形的个数。
思路：寻找三角形构建方式。对于边长为1的三角形个数为1+3+5...通项式n^2。
对于边长大于等于2的三角形个数为1+2+3...通项式n(n-1)/2。对于边长大于等于3的三角形个数，其内部包含的倾斜三角形为其(边长-1)个数。可打表，找出规律C(n,4)。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod=1000000007;
ll n;
ll power_mod(ll a,ll b,ll m){
ll ans=1;
a%=m;
while(b)
{
if(b&1)ans=(ans*a)%m;
a=(a*a)%m;
b>>=1;
}
return ans;
}//power_mod(b,m-2,m)
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
ll ans=(3+n)*(2+n)%mod*power_mod(4,mod-2,mod)%mod*(1+n)%mod*power_mod(3,mod-2,mod)%mod*n%mod*power_mod(2,mod-2,mod)%mod;
printf("%lld\n",ans);
}
} I Magic Potion
题目链接
题意：n个英雄，m个小怪兽。每个英雄只能杀一个怪兽，有k瓶药，一个英雄只能至多嗑一瓶药，喝了药的英雄能多杀一个怪兽。求最多能杀几个怪兽。
思路：建图跑最大流。超级源点连接两个源点。第一个源点表示没有药普通的图，第二个源点表示k瓶药，拆点给其赋值。
#include <bits/stdc++.h>
#define maxn 505
#define inf 0x3f3f3f3f
using namespace std;
int n, m, k;
struct edge {
int to, cap, rev;
};
vector <edge>G[maxn << 1];
int level[maxn << 1];
int iter[maxn << 1];
void add_edge(int from, int to, int cap) {
G[from].push_back({ to, cap, (int)G[to].size() });
G[to].push_back({ from, 0,(int) G[from].size() - 1 });
}
void bfs(int s) {
memset(level, -1, sizeof level);
queue<int>q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int i = 0; i<G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap>0 && level[e.to]<0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
int dfs(int v, int t, int f) {
if (v == t)return f;
for (int &i = iter[v]; i<G[v].size(); i++) {
edge &e = G[v][i];
if (e.cap>0 && level[v]<level[e.to]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d>0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int dinic(int s, int t) {
int flow = 0;
for (;;) {
bfs(s);
if (level[t]<0)return flow;
memset(iter, 0, sizeof iter);
int f;
while ((f = dfs(s, t, inf))>0)
flow += f;
}
}
int S, T, SS, Sk1, Sk2;
void input() {
scanf("%d%d%d", &n, &m, &k);
int i, j, num, x;
S = n + m + 1;
Sk1 = n + m + 2;
Sk2 = n + m + 3;
SS = n + m + 4;
T = n + m + 5;
add_edge(S, Sk1, inf);
add_edge(S, SS, inf);
add_edge(Sk1, Sk2, k);
for (i = 1; i <= n; i++) {
add_edge(SS, i, 1);
add_edge(Sk2, i, 1);
scanf("%d", &num);
for (j = 1; j <= num; j++) {
scanf("%d", &x);
add_edge(i, n + x, 1);
}
}
for (i = 1; i <= m; i++)
add_edge(n + i, T, 1);
}
void solve() {
printf("%d\n", dinic(S, T));
}
int main() {
input();
solve();
} J Prime Game
题目链接
题意：未知。
思路：计算贡献。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
vector<int> v, vec[maxn];
int prime[maxn * 10], num[maxn * 10];
int vis[maxn*10];
int PP[maxn * 10];
int s;
void init() {
for (int i = 2; i <= 1000000; i++) {
if (!vis[i]) {
prime[s++] = i;
PP[i] = s - 1;
for (int j = 2; i * j <= 1000000; j++) {
vis[i * j] = 1;
}
}
}
}
vector<int>id;
int vv[maxn * 10];
void fun(int x,int Id) {
for (int i = 0; prime[i] * prime[i] <= x; i++) {
if (x%prime[i] == 0) {
while (x%prime[i] == 0) {
x /= prime[i];
}
if (!vv[i]) {
vv[i] = 1;
id.push_back(i);
}
vec[i].push_back(Id);
}
if (x == 1)break;
}
if (x!=1) {
if (!vv[PP[x]]) {
vv[PP[x]] = 1;
id.push_back(PP[x]);
}
vec[PP[x]].push_back(Id);
}
}
int main(void) {
int n;
ll ans = 0;
init();
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &num[i]);
fun(num[i], i);
}
for (int i : id) {
/*printf("%d: ", i);
for (int j : vec[i]) {
printf("%d ", j);
}
puts("");
*/
int sz = vec[i].size();
for (int j = 0; j < sz; j++) {
if (j != sz - 1)ans += 1ll * vec[i][j] * (vec[i][j + 1] - vec[i][j]);
else ans += 1ll * vec[i][j] * (n - vec[i][j] + 1);
}
}
cout << ans << endl;
return 0;
}
K Kangaroo Puzzle
题目链接
题意：给出n*m的图，图上的1代表有袋鼠，0代表是墙，要求找到一种方案小于50000步，使得最后图上所有合并为同一个袋鼠。
思路：随机4个方向跑随机。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#include<cstdlib>
#include<ctime>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
char ch[22][22];
int main(void){
srand((int)time(NULL));
int n, m, i, t;
scanf("%d %d",&n,&m);
for(i = 0;i < n;i++){
scanf("%s",ch[i]);
}
for(i = 0;i < 50000;i++){
t = rand() % 4;
if(!t){
printf("U");
}
else if(t == 1){
printf("D");
}
else if(t == 2){
printf("L");
}
else if(t == 3){
printf("R");
}
}
return 0;
}
京公网安备 11010502036488号