第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
19年安徽程序设计省赛题解.docx
A. 机器人足球
#include
#include
#include
using namespace std;
double dis(int x1, int y1, int x2, int y2) {
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main() {
int x, y;
scanf("%d%d", &x, &y);
double d = dis(x,y,100,10)-10;
printf("%.3lf\n",max(d,0.));
}
B. 纸牌识别
#include
#include
#include
using namespace std;
typedef pair pii;
char x;
int y;
int a[200];
set s;
int main() {
a['P']=a['K']=a['H']=a['T']=13;
while (~scanf(" %c%d", &x, &y)) {
if (s.count(pii(x,y))) return puts("GRESKA"),0;
s.insert(pii(x,y));
--a[x];
}
printf("%d %d %d %d\n",a['P'],a['K'],a['H'],a['T']);
}
C. 卡牌对决
#include
#include
#include
#include
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 1e5+10;
int n, a[N];
set Bob, Alice;
int main() {
scanf("%d", &n);
REP(i,1,n) {
scanf("%d",a+i);
Bob.insert(a[i]);
}
REP(i,1,2*n) if (!Bob.count(i)) Alice.insert(i);
int ans = 0;
sort(a+1,a+1+n/2,greater());
REP(i,1,n/2) {
int x = *(--Alice.end());
if (x>a[i]) ++ans, Alice.erase(x);
}
sort(a+1+n/2,a+1+n);
REP(i,1,n/2) {
int x = *Alice.begin();
if (x
#include
#include
#include
#include
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 5e4+10;
int n, m;
struct _ {
int to,w;
_ (int to=0,int w=0) :to(to),w(w) {}
};
vector<_> g1[N], g2[N], g3[N];
ll d1[N], d2[N], d3[N];
int vis[N], u[N], v[N], p[N], q[N];
struct node {
int id;
ll w;
node (int id=0, ll w=0) :id(id),w(w) {}
bool operator < (const node &rhs) const {
return w>rhs.w;
}
};
priority_queue pq;
void dij(vector<_> g[], ll d[], int s) {
memset(d,0x3f,sizeof d1);
memset(vis,0,sizeof vis);
pq.push(node(s,d[s]=0));
while (pq.size()) {
int u = pq.top().id; pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i=0; id1[u[i]]) ++c;
if (d2[v[i]]+q[i]>d2[u[i]]) ++c;
g3[u[i]].pb(_(v[i],c));
}
dij(g3,d3,1);
printf("%lld\n", d3[n]);
}
E.现代艺术
枚举对称轴, 最多O(n)O(n)条, 再暴力O(nlogn)O(nlogn)check, 复杂度
O(nlogn)O(nlogn). 比赛的时候脑抽了把对称轴想成O(n2)O(n2)的了.... 防止浮点误差,
就没用 double 存, 直接对直线暴力约分了
#include
#include
#include
#include
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define x first
#define y second
using namespace std;
typedef pair pii;
int gcd(int x, int y) {return y?gcd(y,x%y):x;}
const int N = 1e3+10;
int n;
pii a[N];
set s;
int chk(int A, int B, int C) {
REP(i,1,n) {
int u = A*a[i].x+B*a[i].y+C;
int v = A*A+B*B;
if (2*u*A%v||2*u*B%v) return 0;
int xx = a[i].x-2*u*A/v, yy = a[i].y-2*u*B/v;
if (!s.count(pii(xx,yy))) return 0;
}
return 1;
}
struct line {
int a,b,c;
line () {}
line (int A, int B, int C) {
if (!A&&!B) throw;
if (!A&&!C) a=c=0,b=1;
else if (!B&&!C) b=c=0,a=1;
else {
if (!C) {
if (A<0) A=-A,B=-B,C=-C;
int g = gcd(A,abs(B));
a = A/g, b = B/g, c = 0;
}
else if (!B) {
if (A<0) A=-A,B=-B,C=-C;
int g = gcd(A,abs(C));
a = A/g, b = 0, c = C/g;
}
else if (!A) {
if (B<0) A=-A,B=-B,C=-C;
int g = gcd(B,abs(C));
a = 0, b = B/g, c = C/g;
}
else {
if (A<0) A=-A,B=-B,C=-C;
int g = gcd(gcd(A,abs(B)),abs(C));
a = A/g, b = B/g, c = C/g;
}
}
}
bool operator < (const line &rhs) const {
if (a!=rhs.a) return a q;
int main() {
scanf("%d", &n);
REP(i,1,n) {
scanf("%d%d", &a[i].x, &a[i].y);
s.insert(a[i]);
}
REP(i,2,n) {
int A = 2*(a[i].x-a[1].x), B = 2*(a[i].y-a[1].y), C = -A*(a[1].x+a[i].x)/2-B*(a[1].y+a[i].y)/2;
if (chk(A,B,C)) q.insert(line(A,B,C));
A = a[i].y-a[1].y, B = a[1].x-a[i].x, C = -A*a[1].x-B*a[1].y;
if (chk(A,B,C)) q.insert(line(A,B,C));
}
printf("%d\n", (int)q.size());
}
F.割草
最小割, 注意到若要改变地形一定是改变一整个连通块, 对SS 向所有低点的连通块连边,
流量为改造整个连通块的花费, 所有高点的连通块向TT 连边, 流量为改造连通块的花费,
相邻连通块连边, 流量为除草机经过两个连通块的燃油花费. 那么显然最小割就为答案.
#include
#include
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;
const int N = 1e6+10, INF = 0x3f3f3f3f;
int n, m, a, b, S, T;
char s[55][55];
struct edge {
int v,next;
ll w;
edge () {}
edge (int v,int next,ll w) :v(v),w(w),next(next) {}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue Q;
void add(int u, int v, ll w) {
e[++cnt] = edge(v,head[u],w);
head[u] = cnt;
e[++cnt] = edge(u,head[v],0);
head[v] = cnt;
}
int bfs() {
REP(i,1,T) dep[i]=INF,vis[i]=0,cur[i]=head[i];
dep[S]=0,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
for (int i=head[u]; i; i=e[i].next) {
if (dep[e[i].v]>dep[u]+1&&e[i].w) {
dep[e[i].v]=dep[u]+1;
Q.push(e[i].v);
}
}
}
return dep[T]!=INF;
}
ll dfs(int x, ll w) {
if (x==T) return w;
ll used = 0;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].v]==dep[x]+1&&e[i].w) {
int flow = dfs(e[i].v,min(w-used,e[i].w));
if (flow) {
used += flow;
e[i].w -= flow;
e[i^1].w += flow;
if (used==w) break;
}
}
}
return used;
}
ll dinic() {
ll ans = 0;
while (bfs()) ans+=dfs(S,1e18);
return ans;
}
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int fa[N], sz[N], cost[3000][3000];
int id(int x, int y) {
return (x-1)*m+y;
}
int Find(int x) {return fa[x]?fa[x]=Find(fa[x]):x;}
void add(int x, int y) {
x = Find(x), y = Find(y);
if (x!=y) fa[x]=y,sz[y]+=sz[x];
}
int main() {
scanf("%d%d%d%d", &n, &m, &a, &b);
REP(i,1,n) scanf("%s",s[i]+1);
REP(i,1,n) REP(j,1,m) sz[id(i,j)]=1;
REP(i,1,n) REP(j,1,m) {
REP(k,0,3) {
int x=i+dx[k],y=j+dy[k];
if (s[i][j]==s[x][y]) add(id(i,j),id(x,y));
}
}
REP(i,1,n) REP(j,1,m) {
if (i!=n&&s[i][j]!=s[i+1][j]) {
int u = Find(id(i,j)), v = Find(id(i+1,j));
if (s[i][j]=='.') swap(u,v);
cost[u][v] += a;
}
if (j!=m&&s[i][j]!=s[i][j+1]) {
int u = Find(id(i,j)), v = Find(id(i,j+1));
if (s[i][j]=='.') swap(u,v);
cost[u][v] += a;
}
}
REP(i,1,n*m) REP(j,1,n*m) if (cost[i][j]) add(i,j,cost[i][j]);
S = n*m+1, T = S+1;
REP(i,1,n) REP(j,1,m) if (Find(id(i,j))==id(i,j)) {
if (s[i][j]=='#') add(S,id(i,j),(ll)sz[id(i,j)]*b);
else add(id(i,j),T,(ll)sz[id(i,j)]*b);
}
printf("%lld\n", dinic());
}
G.括号序列
dpdp 求出长为xx, 左括号比右括号多yy 个时的方案数. 然后从前往后枚举, 若放'('的方案
数不少于kk 则放'(', 否则放')'.
注意方案数是指数级, 会爆 long long.
#include
#define REP(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;
const int N = 2010;
int n, k;
ll f[N][N];
char ans[N];
int main() {
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
