赛码"BestCoder"杯中国大学生程序设计冠军赛
发布时间
阅读量：
阅读量
渣渣一枚
完成了四道题。简单总结一下吧：整体难度适中。题目链接 1001 这个题目的描述类似于HDU之前的问题，在今年的暑假期间无法通过AC（即正确解答）。具体来说，在选择三个选项时，则需要从左右两边进行贪心算法的选择。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define MOD 4294967296
using namespace std;
typedef unsigned int LL;
int T;
int n;
const int N=10000005;
LL s1,e1;
LL L1,R1,L2,R2;
LL minL,minR,maxL,maxR;
LL a,b,c,d;
LL p[N],q[N];
bool flag;
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("test.in","r",stdin);
#endif
scanf("%d",&T);
while(T--)
{
cin>>n>>s1>>e1>>a>>b>>c>>d;
p[1]=s1;
q[1]=e1;
for(int i=2;i<=n;i++)
{
p[i]=p[i-1]*a+b;
q[i]=q[i-1]*c+d;
}
for(int i=1;i<=n;i++)
{
if(p[i]>q[i])
{
swap(p[i],q[i]);
}
if(i==1)
{
minL=maxL=p[1];
minR=maxR=q[1];
}
else
{
if(q[i]<minR)
{
minL=p[i];
minR=q[i];
}
if(p[i]>maxL)
{
maxL=p[i];
maxR=q[i];
}
}
}
flag=false;
for(int i=1;i<=n;i++)
{
if(p[i]>minR&&q[i]<maxL)
{
flag=true;
break;
}
}
printf("%s\n",flag?"YES":"NO");
}
return 0;
}
代码解读1002
计算图中的奇数环与偶数环数量，并观察到这一段代码具有很高的参考价值…
官方题解通常采用二分图染色法配合深度优先搜索（Tarjan算法）来解决这类问题。
其中一种常用的方法是通过染色法进行判断。
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <queue>
#include <bitset>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 100005;
const int maxm = 600005;
struct Edge
{
int v, vis;
Edge *next;
}*H[maxn], E[maxm], *edges;
int vis[maxn];
int n, m, ok1, ok2;
void read(int& x)
{
x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
void addedges(int u, int v)
{
edges->vis = 0;
edges->v = v;
edges->next = H[u];
H[u] = edges++;
}
void init()
{
edges = E;
memset(H, 0, sizeof H);
memset(vis, -1, sizeof vis);
}
void dfs(int u, int fa)
{
for(Edge *e = H[u]; e; e = e->next) if(e->v != fa){
int v = e->v;
if(vis[v] != -1) {
if(vis[v] == vis[u]) ok1 = 1;
else ok2 = 1;
}
if(!e->vis) e->vis = 1, vis[v] = vis[u] ^ 1, dfs(v, u);///改变状态,0->1 1->0 二分图染色
}
vis[u] = -1;///标志在最后修改,说明这个点仍可用于其他边
}
void work()
{
int u, v;
init();
scanf("%d%d", &n, &m);
//read(n), read(m);
for(int i = 1; i <= m; i++) {
// read(u), read(v);
scanf("%d%d", &u, &v);
addedges(u, v);
addedges(v, u);
}
ok1 = 0, ok2 = 0;
for(int i = 1; i <= n; i++) if(vis[i] == -1) {
vis[i] = 0;
dfs(i, 0);
}
if(ok1) printf("YES\n");
else printf("NO\n");
if(ok2) printf("YES\n");
else printf("NO\n");
}
int main()
{
int _;
scanf("%d", &_);
while(_--) work();
return 0;
}
代码解读 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#pragma comment(linker, "/STACK:102400000,102400000")
#define LL long long
using namespace std;
const int N = 100100, M = 600100;
int head[N], tot, vis[N], b[M], c[N];
int n, m;
struct edge {
int u, v, nx, id;
edge (int u = 0, int v = 0, int nx = 0, int id = 0) : u (u), v (v), nx (nx), id (id) {}
} e[M];
void init () {
memset (head, -1, sizeof (int) * (n + 5));
tot = 0;
}
void add (int u, int v, int id) {
e[tot] = edge (u, v, head[u], id);
head[u] = tot++;
}
int ok, ok2;
void dfs (int u, int fa) {
if (vis[u]) {
if (vis[u] == 1) ok = 1;
return;
}
vis[u] = 1;
for (int i = head[u]; ~i; i = e[i].nx) {
int v = e[i].v;
if (v == fa) continue;
if (c[v] == 0) {
c[v] = 3 - c[u];
} else if (c[v] == c[u]) {
ok2 = 0;
}
dfs (v, u);
}
vis[u] = -1;
}
void solve () {
ok = 0;
ok2 = 1;
memset (c, 0, sizeof (int) * (n + 5));
memset (vis, 0, sizeof (int) * (n + 5));
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
c[i] = 1;
dfs (i, -1);
}
}
}
int id[N], pre[N], low[N], s[N], stop, cnt, scnt;
void tarjan (int v, int n, int fa) {
int t, minc = low[v] = pre[v] = cnt++;
s[stop++] = v;
for (int i = head[v]; ~i; i = e[i].nx) {
if ((fa ^ 1) == i) continue;
int to = e[i].v;
if (pre[to] == -1) tarjan(to, n, i);
if (low[to] < minc) minc = low[to];
}
if (minc < low[v]) {
low[v] = minc; return;
}
do {
id[ t = s[--stop]] = scnt; low[t] = n;///这句的厉害
} while (t != v);
++scnt;///双连通分量个数
}
int cntn, cntm;
void dfs2 (int u) {
// cout << u << endl;
if (vis[u]) return;
cntn++;
vis[u] = 1;
for (int i = head[u]; ~i; i = e[i].nx) if (!b[i]) {
int v = e[i].v;
cntm++;
dfs2 (v);
}
}
int solve2 () {
stop = cnt = scnt = 0;
memset (pre, -1, sizeof (int) * (n + 5));
for (int i = 1; i <= n; i++) {
if (pre[i] == -1) {
tarjan(i, n, -1);
}
}
for (int i = 0; i < 2 * m; i++) {
int u = id[e[i].u], v = id[e[i].v];
b[i] = (u != v);///该边是否在同一个连通分量中,0在,1不在
}
memset (vis, 0, sizeof (int) * (n + 5));
for (int i = 1; i <= n; i++) if (!vis[i]) {
cntn = cntm = 0;
dfs2 (i);
// cout << cntn << ' ' << cntm << endl;
if (cntn == 1) continue;
if (cntn * 2 != cntm || cntn % 2 == 0) return 0;///大联通分量内部可能有小的只用判断奇奇(点数为偶)因此，除非一个双联通分量仅仅是一个奇环，那么其中必定存在偶环
}
return 1;
}
int main () {
// freopen ("in.txt", "r", stdin);
int T;
cin >> T;
while (T--) {
cin >> n >> m;
init ();
int u, v;
for (int i = 1; i <= m; i++) {
scanf ("%d%d", &u, &v);
add (u, v, i);
add (v, u, i);
}
solve ();///先用染色法判断是否为二分图,不是的话且联通那么必定是只有偶数个
if (ok2) {
printf ("NO\n");
if (ok) {
printf ("YES\n");
} else {
printf ("NO\n");
}
} else {
printf ("YES\n");
if (solve2 ()) {
printf ("NO\n");
} else {
printf ("YES\n");
}
}
}
}
代码解读1005
这道是递推题目,着实学了一下,思路和HDU4089很像.这个递推没想出来有点伤心.当有1个人的时候情况可知,那么人数更多的时候可以推过来,于是 dp[i][j] 当有i个人时,j能否赢.O(n^3)
Tips: 当有环或取模时,编号从0开始,避免了整除等情况特殊处理.
#include "stdio.h"
#include "iostream"
#include "string.h"
#include "stdlib.h"
#include "algorithm"
#include "math.h"
#include <queue>
using namespace std;
const int MAXN=210;
int dp[MAXN][MAXN];
typedef long long LL;
int a[MAXN];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i<=m;i++) scanf("%d",a+i);
memset(dp,0,sizeof(dp));
dp[1][0] = 1;
for(int i = 2;i<=n;i++){
for(int j = 0;j<n;j++) if(dp[i-1][j])
for(int k = 1;k<=m;k++)
dp[i][ (j+a[k])%i ] = 1;
}
int cnt = 0;
for(int i = 0;i<n;i++) if(dp[n][i])
a[cnt++] = i+1;
printf("%d\n",cnt);
for(int i = 0;i<cnt;i++)
if(i==cnt-1) printf("%d\n",a[i]);
else printf("%d ",a[i]);
}
return 0;
}
代码解读图论知识已经遗忘得差不多了，在这个问题中每条边只能被访问一次。我在处理双向边时需要考虑两个顶点之间的先后顺序问题。没想到这个可以用并查集合并处理，并将它们视为一个整体来处理。这样如果接收的顶点位于同一个连通分量中，则返回YES；否则，则会形成一个有向无环图（DAG），可以通过拓扑排序来解决。PS: 广度优先搜索（BFS）的应用非常强大，在之前的学习中发现两层循环实现这类算法非常繁琐。
#include "stdio.h"
#include "iostream"
#include "string.h"
#include "stdlib.h"
#include "algorithm"
#include "math.h"
#include <queue>
using namespace std;
const int MAXN=1000005;
const int MAXV=1010000;
int pre[MAXV],m,a,b;
bool root[MAXV];
typedef long long LL;
int ned,ans,fa[MAXN],son[MAXN];
int n,m1,m2;
queue<int> q;
int mm1[MAXN][2],mm2[MAXN];
struct EDGE{
int p;
struct EDGE *nex;
}edge[2*MAXN],*head[MAXN];
void init()
{
if(!q.empty())
q.pop();
ned=0;
for(int i=0;i<MAXN;i++)
head[i]=NULL;
memset(son,0,sizeof(son));
memset(mm1,0,sizeof(mm1));
memset(mm2,0,sizeof(mm2));
for(int i=1;i<=MAXN;i++)
pre[i]=i;
memset(root,0,sizeof(root));
ans=0;
}
void addedge(int s,int e)
{
edge[ned].p=e;edge[ned].nex=head[s];
head[s]=&edge[ned];
ned++;
}
int find(int x)
{
int r=pre[x];
while(pre[r]!=r)
r=pre[r];
int i=x,j;
while(pre[i]!=i) //压缩路径优化
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}
void join(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
pre[fy]=fx;
}
int main()
{
int flag;
int T;
cin>>T;
while(T--)
{
flag=0;
init();
cin>>n>>m2>>m1;
int aa,bb;
for(int i=0;i<m2;i++)
{
scanf("%d%d",&aa,&bb);
if(find(aa)==find(bb))
{
flag=1;
}
else
{
join(aa,bb);
}
}
for(int i=0;i<m1;i++)
{
scanf("%d%d",&mm1[i][0],&mm1[i][1]);
}
for(int i=0;i<m1;i++)
{
aa=find(mm1[i][0]);
bb=find(mm1[i][1]);
if(aa==bb)
{
flag=1;
break;
}
else
{
addedge(aa,bb);
}
}
if(flag==1)
{
printf("YES\n");
continue;
}
memset(fa,0,sizeof(fa));
for(int i=0;i<ned;i++)
{
fa[edge[i].p]++;
}
for(int i=1;i<=n;i++)
{
if(fa[i]==0)
{
q.push(i);
}
}
while(!q.empty())
{
int x=q.front(),f;
q.pop();
for(struct EDGE *w=head[x];w!=NULL;w=w->nex)
{
int x=w->p;
fa[x]--;
if(fa[x]==0)
q.push(x);
}
}
for(int i=1;i<=n;i++)
{
if(fa[i]!=0)
{
flag=1;
break;
}
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
代码解读1010
这个问题看似简单, 但初学者往往会被多个数据点之间的关系所困扰. 具体来说, 当区域之间不重叠时, 其对应的数量为1; 而当区域发生重叠时, 则应取各区域数量的最大公约数（LCM）. 满足条件的情况包括: 当范围较大时其最大公约数（GCD）值较大; 当范围相等但各区域数量互质时其最大公约数（GCD）值为1; 以及仅考虑单个区域的情况.
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 1101
using namespace std;
struct P{
int l,r,x;
bool operator < (const P &a) const{
if(l==a.l) return r<a.r;
return l<a.l;
}
}p[MAXN];
long long a[MAXN];
long long GCD(long long a,long long b){
return b==0?a:GCD(b,a%b);
}
int main() {
int T,N,Q;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&Q);
for(int i = 1;i<=Q;i++)
scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].x);
int tag = 1;
for(int i = 1;i<=Q && tag;i++){
for(int j = 1;j<=Q && tag;j++){
if(p[i].l==p[j].l && p[i].r==p[j].r && p[i].x != p[j].x)
tag = 0;
if(p[i].l>p[j].l && p[i].r<p[j].r && p[i].x < p[j].x)
tag = 0;
}
}
if(tag==0){
printf("Stupid BrotherK!\n");
continue;
}
for(int i = 1;i<=N;i++) a[i] = 1;
for(int i = 1;i<=N;i++){
for(int j = 1;j<=Q;j++) if(i>=p[j].l && i<=p[j].r)
a[i] = a[i] / GCD(a[i],p[j].x) * p[j].x;
}
for(int i = 1;i<=N;i++)
if(i==N) printf("%I64d\n",a[i]);
else printf("%I64d ",a[i]);
}
return 0;
}
代码解读全部评论 (0)
还没有任何评论哟~