A : 计划日
Progress Bar
时间限制:3 Sec 内存限制:256 MiB
提交:237 答案正确:75
题目描述
为什么花那么多时间、精力还是学不好学不通，如何把握各科目的重难点，期中和期末如何梳理本学期各知识点及内部联系……在孩子学习的过程中，我们该如何帮助孩子快速提高成绩呢？
打造名校进阶计划，让孩子会学习、会考试，实现名校梦想！
Dr. Kong, 作为一名从教多年的老师，跟踪了大量成绩好的学生，发现他们的学习习惯非常规律，有方法、有计划、有目标、有总结。比如：已考上**大学的李明同学,从小学开始订学习计划，达成目标。每经过N天就检查目标是否完成，写总结，并确定下一个学习目标。
已知李明在YYYY年MM月DD日星期W订了学习计划，现在想看看李明N天后的完成情况和个人总结，你能告诉我那天的日期和星期几吗？
输入
第一行： T 表示以下有T组测试数据 （ 1≤ T ≤8 ）
对每组数据， 占一行：
YYYYMMDD W N （20000101≤YYYYMMDD≤20180527 1≤W≤ 7 1 ≤N≤ 8000 ）
输出
对每组测试数据，输出占一行，格式为：YYYYMMDD W ( 中间一个空格 )
样例输入
复制
2
20180527 7 1
20180214 3 289
样例输出
复制
20180528 1
20181130 5
写逻辑去算？麻烦死了，直接模拟算了。。。
#include<bits/stdc++.h>
using namespace std;
int y,m,d;
int dd,w;
int T;
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool IsLeapYear(int y)
{
if(y%400==0||(y%4==0&&y%100))
{
return 1;
}
return 0;
}
void fresh()
{
bool leap = IsLeapYear(y);
if(leap)mon[2]=29;
else mon[2]=28;
}
void calc()
{
w=(w-1+dd)%7+1;
fresh();
while(dd)
{
d++;
if(d>mon[m])
{
d=1;
m++;
if(m>12)
{
m=1;
y++;
fresh();
}
}
dd--;
}
}
void out()
{
printf("%4d%02d%02d %d\n",y,m,d,w);
}
int main()
{
freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%4d%2d%2d %d %d",&y,&m,&d,&w,&dd);
calc();
out();
}
return 0;
} B : 治安管理
Progress Bar
时间限制:3 Sec 内存限制:128 MiB
提交:135 答案正确:35
题目描述
SZ市是中国改革开放建立的经济特区，是中国改革开放的窗口，已发展为有一定影响力的国际化城市，创造了举世瞩目的“SZ速度”。SZ市海、陆、空、铁口岸俱全，是中国拥有口岸数量最多、出入境人员最多、车流量最大的口岸城市.
为了维护SZ经济特区社会治安秩序，保障特区改革开放和经济建设的顺利进行, 特别设立了SZ社会治安综合治理委员会主管特区的社会治安综合治理工作。公安机关是社会治安的主管部门，依照法律、法规的规定进行治安行政管理，打击扰乱社会治安的违法犯罪行为，维护社会秩序。
YYH大型活动将在[S,F）这段时间举行，现要求活动期间任何时刻巡逻的警察人数不少于M人。公安机关将有N名警察在维护活动的安全，每人巡逻时间为[ai,bi)。请你检查目前的值班安排，是否符合要求。若满足要求，输出YES，并输出某个时刻同时巡逻的最多人数；若不满足要求，输出NO，并输出某个时刻同时巡逻的最少人数。
输入
第一行： T 表示以下有T组测试数据 （ 1≤ T ≤5 ）
对每组数据，
第一行：N M S F ( 1≤N≤10000 1≤M ≤1000 0≤S0）
第二行，a1 a2 …. an 警察巡逻起始时间
第三行，b1 b2 …. bn 警察巡逻结束时间 ( 0≤ai0 i=1…. n）
输出
对每组测试数据，输出占一行。若满足要求，输出YES，并输出某个时刻同时巡逻的最多人数；若不满足要求，输出NO，并输出某个时刻同时巡逻的最少人数。（中间一个空格）
样例输入
复制
2
5 2 0 10
0 0 2 7 6
6 2 7 10 10
10 2 6 11
1 3 5 7 9 2 4 6 8 10
2 4 6 8 10 3 5 7 9 11
样例输出
复制
YES 2
NO 1
数组少写了0，然后一直runntime error。。。。。
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn=100001;
int T;
int a[maxn];
int n,m,s,f;
int mina,maxa;
int t;
int main()
{
freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof(a));
mina = inf;
maxa = 0;
scanf("%d %d %d %d",&n,&m,&s,&f);
for(int i=0;i!=n;i++)
{
scanf("%d",&t);
a[t]++;
}
for(int i=0;i!=n;i++)
{
scanf("%d",&t);
a[t]--;
}
for(int i=1;i<=f;i++)
{
a[i]+=a[i-1];
}
mina=maxa=a[s];
for(int i=s;i<f;i++)
{
// cout<<i<<" "<<a[i]<<endl;
mina=min(mina,a[i]);
maxa=max(maxa,a[i]);
}
if(mina<m)
{
cout<<"NO "<<mina<<endl;
}
else
{
cout<<"YES "<<maxa<<endl;
}
}
return 0;
} C : 山区修路
Progress Bar
时间限制:3 Sec 内存限制:128 MiB
提交:104 答案正确:51
题目描述
SNJ位于HB省西部一片群峰耸立的高大山地，横亘于A江、B水之间，方圆数千平方公里，相传上古的神医在此搭架上山采药而得名。景区山峰均在海拔3000米以上，堪称"华中屋脊"。SNJ是以秀绿的亚高山自然风光，多样的动植物种，人与自然和谐共存为主题的森林生态区。
SNJ处于中国地势第二阶梯的东部边缘，由大巴山脉东延的余脉组成中高山地貌，区内山体高大，高低不平。 交通十分不便。
最近，HB省决定修一条从YC市通往SNJ风景区的高速公路。经过勘测分析，途中需要经过高度分别为H1，H2，……,Hn的N个山区。由于高低不平，除正常的修路开支外，每段还要多出高度差|Hi - Hi-1|*X万元的斜坡费用。Dr. Kong 决定通过填高一些区域的高度来降低总的费用。当然填高也是需要一些费用的。每填高Y单位，需要付出Y2万元费用。
你能否帮Dr. Kong做出一个规划，通过部分填高工程改造，使得总的费用降下来。
输入
第一行： T 表示以下有T组测试数据 （ 1≤ T ≤8 ）
对每组测试数据，
第一行：N X （2 ≤ N ≤100，000 1≤ X ≤100）
第二行：N个整数，分别表示N个区域的高度Hi ( 1<=Hi<=100 , i=1…. n)
输出
对每组测试数据，输出占一行，一个整数，即经过部分填高工程改造后的最少费用。
样例输入
复制
1
5 2
2 3 5 1 4
样例输出
复制
15
动态规划，当我要垫高h1时，前一座垫高多少我们花费最低。
输入的时候记录一下最高的那座山的高度。
可知这座山一定不会再垫高了，因为这座山垫高必将带来花费的增加。
按我们所有的山垫高后的高度都不会超过这个高度。
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn=100001;
int T,n,x,th;
int h[maxn];
int dp[maxn][101];
int maxh;
int main()
{
freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
maxh=0;
scanf("%d %d",&n,&x);
for(int i=0;i!=n;i++)
{
scanf("%d",&h[i]);
maxh=max(maxh,h[i]);
}
for(int i=h[0];i<=maxh;i++)
{
int dh=i-h[0];
dp[0][i]=dh*dh;
}
for(int i=1;i!=n;i++)
{
for(int j=h[i];j<=maxh;j++)
{
int y=j-h[i];
dp[i][j]=inf;
for(int k=h[i-1];k<=maxh;k++)
{
int dh=abs(j-k);
dp[i][j]=min(dh*x+y*y+dp[i-1][k],dp[i][j]);
}
}
}
int ans=inf;
for(int i=h[n-1];i<=maxh;i++)
{
ans=min(dp[n-1][i],ans);
}
cout<<ans<<endl;
}
return 0;
} D : 求XF+闭包
Progress Bar
时间限制:3 Sec 内存限制:128 MiB
提交:38 答案正确:16
题目描述
如何设计一个好的数据库不仅仅是一个理论研究问题，也是一个实际应用问题。在关系数据库中不满足规范化理论的数据库设计会存在冗余、插入异常、删除异常等现象。
设R(U)是一个关系模式，U={ A1,A2, ……, An}。其中Ai是关系的属性，X,Y是U的子集。函数依赖 XàY 定义了数据库中属性集X与Y的依赖关系。根据Armstrong公理，函数依赖满足： （1） 自反律：若Ai∈X, 则 XàAi . 特别地，Ai àAi .
（2） 增广律：若 XàY, 则 ZXàZY. (ZX 是指集合Z与X的并集 )
（3） 传递律：若 XàY, YàZ, 则 XàZ.
（4） 分解律：若 XàY, 则 XàAi ( 若属性Ai∈Y )
（5） 合并律：若 XàY, XàZ, 则 XàYZ.
已知 F 是关系模式R(U)上的函数依赖集，利用Armstrong公理系统可以推导出更多的函数依赖。设X是属性集U={ A1,A2, ……, An} 的子集， 定义X关于F的闭包XF+
XF+={ Ai | 若Xà Ai可以通过Armstrong公理导出}
对于给定的U , F ,X, 请求出XF+
输入
第一行： T 表示以下有T组测试数据 （ 1≤T ≤5 ）
对每组数据，
第1行： n m k n 表示U中属性个数（ 1≤n≤26 ）, 用大写字母表示
m表示X中属性个数（ 1≤m≤26 ）
k个函数依赖 （1≤ k ≤ 20 ）
第2行: 字符串U n个大写字母 第3行: 字符串X m个大写字母
接下来有K行，每行有两个字符串 S T，用一个空格隔开。 表示 SàT
输出
对每组测试数据，输出占一行输出XF+，要求按字母序输出。
样例输入
复制
1
6 2 4
ABGDCI
AD
A B
BD I
AG C
C D
样例输出
复制
ABDI
就是给定了一些字符集，然后给出了一些产生式子。
如果产生式的前边的那个字符串我们能够组出来的话，我们就能得到后面所有的字符。
我们就把后面的字符加进我们已经有的字符集来，直到我们不能通过新的式子加入新字符为止。
最后输出集合里边的字符集就好。
#include<bits/stdc++.h>
using namespace std;
int n,m,k,T;
string s,ss;
set<char> ans;
map<string,string> func;
map<string,int> vis;
bool flag=1;
bool check(const string &a)
{
for(int i=0;i!=a.size();i++)
{
if(ans.find(a[i])==ans.end())return 0;
}
return 1;
}
void outans()
{
set<char>::iterator it;
for(it=ans.begin();it!=ans.end();it++)
{
cout<<*it;
}
cout<<endl;
}
int main()
{
while(~scanf("%d",&T))
{
while(T--)
{
ans.clear();
func.clear();
vis.clear();
scanf("%d %d %d ",&n,&m,&k);
cin>>s>>s;
for(int i=0;i!=s.size();i++)
{
ans.insert(s[i]);
}
for(int i=0;i!=k;i++)
{
cin>>s>>ss;
func[s]=ss;
vis[s]=0;
}
flag=1;
while(flag)
{
flag=0;
map<string,string>::iterator it;
for(it=func.begin();it!=func.end();it++)
{
if(!vis[it->first]&&check(it->first))
{
flag=1;
vis[it->first]=1;
for(int i=0;i!=it->second.size();i++)
{
ans.insert(it->second[i]);
}
}
}
}
outans();
}
}
return 0;
} E : 物流配送
Progress Bar
时间限制:8 Sec 内存限制:128 MiB
提交:64 答案正确:20
题目描述
物流配送是物流活动中一种非单一的业务形式，它与物品流动、资金流动紧密结合。备货是配送的准备工作或基础工作，备货工作包括筹集货源、订货或购货、集货、进货及有关的质量检查、结算、交接等。配送的优势之一，就是可以集中用户的需求进行一定规模的备货。备货是决定配送成败的初期工作，如果备货成本太高，会大大降低配送的效益。配送中的储存有储备及暂存两种形态。配送储备是按一定时期的配送经营要求，形成的对配送的资源保证。这种类型的储备数量较大，储备结构也较完善，视货源及到货情况，可以有计划地确定周转储备及保险储备结构及数量。
Dr. Kong 所在的研究团队准备为Hai-E集团开发一个物流配送管理系统。已知Hai-E集团已经在全国各地建立了n个货物仓库基地，任意两个基地的货物可以相互调配。现在需要根据用户订货要求，来重新调配每个基地的货物数量。为了节流开源，希望对整个物流配送体系实行统一的货物管理和调度，能够提供一个全面完善的物流仓储配送解决方案，以减少物流配送过程中成本、人力、时间。
输入
第一行： n （1 ≤ n ≤ 1000）
第2行： a1 a2 …… an 表示n个基地当前的物品数量 (0≤ ai ≤ 106 )
第3行： b1 b2 …… bn 表示调配后，每个基地i应不少于bi个物品 (0≤ bi ≤ 106)
接下来n-1行，每行三个整数： i j k 表示从第i基地调配一个物品到第j基地需要花费为k，或 从第j基地调配一个物品到第i基地需要花费为k。(0≤ k ≤ 106)
输出
输出配送后的最小费用。
已知： a1+a2+…+an >=b1+b2+…+bn
样例输入
复制
6
0 1 2 2 0 0
0 0 1 1 1 1
1 2 2
1 3 5
1 4 1
2 5 5
2 6 1
样例输出
复制
9
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
//设计了边的结构体，用来在Spfa时使用
//V表示下一个点，Cap表示总容量capacity，Cost用来表示这条路单位货物运输需要花费多少，
//Flow表示现在这条路加上了多少流量，Next表示我们大家都是以U点开始的集合的，上一个路
//这份代码的巧妙就是用next把本来分散的路径数据通过Next划分成了，以不同点开始的路的集合
//Next指的是上一条以U点开始的路径在edges数组的第几行。
//详细解释见Addedge（）
struct Link
{
long long V, Cap, Cost, Flow, Next;
};
//N指的是有几个仓库
int N;
//A用来记录有货物的地点，B记录哪里需要货物
int A[maxn], B[maxn];
//Head用来记录以U开始的边的最后一条在edges数组中的第几行
int Head[maxn];
//Path用来记录在增广时用Spfa搜出来的路径
int Path[maxn];
//Dis用来记录到超级源点的距离，就是dijkstra里边用的那个Dis
int Dis[maxn];
//Vis是在Spfa广搜时用来标记时用的
bool Vis[maxn];
//Tot用来记录总共我们存到edges中了几条边
int Tot;
//用来存边
Link edges[maxn << 3];
//初始化，把路径总数Tot初始话为0
//把Head全部初始化为-1，表示还没有从U点开始的路径
void Init()
{
Tot = 0;
memset(Head, -1, sizeof(Head));
}
//加边函数，精华
void AddEdge(int U, int V, long long Cap, long long Cost)
{
//Tot这一行存进去我们要加的这条边，并把以U开始的上一条边的行数存在了Next中，
//这样我们很容易遍历到所有以U开始的边，从而进行深搜。
//那么疑问来了我们为啥不直接开vector<int> edges[maxn]这样储存呢，这样又清晰，又省内存，也快
//因为我们在网络流问题中很容易涉及到残余网络的反向边，如果我们采用vector存
//那么我们在找反向边时该怎么办呢?
//扫描一遍edges[v]？ 慢死了
//下面这份代码处理找反向边的神仙操作就来了
edges[Tot] = Link {V, Cap, Cost, 0, Head[U]};
Head[U] = Tot++;
//正向加了一条偶数行的正向边后，又加了一条行数为奇数的反向边
//花费为负值，用来在取消流时使用。但反向边一开始时是没有容量的，即不能直接在这条边上加流
//只能取消这上面由于反向加边产生的流
//由于我们这样的建边方式，那么edges[i]这条边的反向边就是edges[i^1]，不解释，可好玩
edges[Tot] = Link {U, 0, -Cost, 0, Head[V]};
Head[V] = Tot++;
}
//可知我们的图总共分四层
//超级源点一层，
//有货的一层
//缺货的一层
//超级汇点一层
//我们使用广搜，必定是严格按照一层一层的搜索的，不解释
//那么我们怎么才能正确的进行增广呢？
//我们的最终目的是要找到最小费用的最大流
//那么我们是不是可以在找增广路径的时候使用贪心的思想，
//假如找到的每一条增广路径都是当前能找到的花费最小的增广路，那么我们的最终花费不就一定是最小的了吗
//因为如果我们加了一条不是当前最小花费的流，那么他必定会反向加边，
//那么我们在下一轮的搜索中必定会找到，这个不太聪明的流而反向取消他
//所以贪心的去搜索当前花费最小的流就好
//那么我们怎么找当前花费最小的路径呀，我们用Path来标记到当前节点，运输单位物资花费最小的点
//用Dis来保存到当前节点，运输单位物资花费最小的值
//当前点的花费一定是 所有上一层节点中的（Dis+到当前节点花费）的最小值。
//然后我们就相当于构建了一个已经在最小花费的集合的点集，和不在最小花费点集的一个点集
//然后使用当前这个点来优化那些不在当前最小花费点集的那些点。
//思想就是dijkstra的最短路径思想
//最终我们就找到了一条从超级源点，到超级汇点的最小单位花费的一条路径。
//之后进行增广就好啦
bool Spfa(int Start, int End)
{
memset(Dis, INF, sizeof(Dis));
memset(Vis, false, sizeof(Vis));
memset(Path, -1, sizeof(Path));
Dis[Start] = 0;
Vis[Start] = true;
std::queue<int> Que;
while (!Que.empty())
{
Que.pop();
}
Que.push(Start);
while (!Que.empty())
{
int U = Que.front();
Que.pop();
Vis[U] = false;
for (int i = Head[U]; i != -1; i = edges[i].Next)
{
int V = edges[i].V;
if (edges[i].Cap > edges[i].Flow && Dis[V] > Dis[U] + edges[i].Cost)
{
Dis[V] = Dis[U] + edges[i].Cost;
Path[V] = i;
if (!Vis[V])
{
Vis[V] = true;
Que.push(V);
}
}
}
}
return Path[End] != -1;
}
//这个没啥好解释的嘛
//就是使用Spfa找到花费最小的那个路，进行增广就好
//让后正向减边，反向加边就好
//至于找反向边按个骚操作也解释过了
int MinCostMaxFlow(int Start, int End, long long &MinCost)
{
int MaxFlow = 0;
MinCost = 0;
while (Spfa(Start, End))
{
int Min = INF;
for (int i = Path[End]; i != -1; i = Path[edges[i ^ 1].V])
{
if (edges[i].Cap - edges[i].Flow < Min) {
Min = edges[i].Cap - edges[i].Flow;
}
}
for (int i = Path[End]; i != -1; i = Path[edges[i ^ 1].V]) {
edges[i].Flow += Min;
edges[i ^ 1].Flow -= Min;
MinCost += edges[i].Cost * Min;
}
MaxFlow += Min;
}
return MaxFlow;
}
int main(int argc, char *argv[])
{
while (~scanf("%d", &N))
{
Init();//head=-1 Tot=0
for (int i = 1; i <= N; ++i)
{
scanf("%d", &A[i]);
}
for (int i = 1; i <= N; ++i)
{
scanf("%d", &B[i]);
}
for(int i=1;i<=N;i++)
{
if(B[i]&&A[i])
{
int t=min(A[i],B[i]);
A[i]-=t;
B[i]-=t;
}
if(A[i])
AddEdge(0, i, A[i], 0);//初始化超级源点到a
if(B[i])
AddEdge(i, N + 1, B[i], 0);//初始化b到超级汇点
}
//添加题目给的费用路径
for (int i = 1, U, V, C; i < N; ++i)
{
scanf("%d%d%d", &U, &V, &C);
AddEdge(U, V, INF, C);
AddEdge(V, U, INF, C);
}
long long MinCost;
//计算最小费用最大流
MinCostMaxFlow(0, N + 1, MinCost);
printf("%lld\n", MinCost);
}
return 0;
} 2309: Gene mutation
时间限制: 3 Sec 内存限制: 128 MB
提交: 403 解决: 217
[提交] [状态] [讨论版] [命题人:admin]
题目描述
Gene mutation is the sudden and inheritable mutation of genomic DNA molecules. From the molecular level, gene mutation refers to the change of the composition or sequence of base pairs in the structure of a gene. Although the gene is very stable, it can reproduce itself accurately when the cell divides. Under certain conditions, the gene can also suddenly change from its original existence to another new form of existence.
A genome sequence might provide answers to major questions about the biology and evolutionary history of an organism. A 2010 study found a gene sequence in the skin of cuttlefish similar to those in the eye’s retina. If the gene matches, it can be used to treat certain diseases of the eye.
A gene sequence in the skin of cuttlefish is specified by a sequence of distinct integers (Y1,Y2, …Yc). it may be mutated. Even if these integers are transposed ( increased or decreased by a common amount ) , or re-ordered , it is still a gene sequence of cuttlefish. For example, if “4 6 7” is a gene sequence of cuttlefish, then “3 5 6” (-1), “6 8 9” ( +2), “6 4 7” (re-ordered), and “5 3 6” (transposed and re-ordered) are also ruminant a gene sequence of cuttlefish.
Your task is to determine that there are several matching points at most in a gene sequence of the eye’s retina (X1,X2, …, Xn)
输入
The first line of the input contains one integer T, which is the number of test cases (1<=T<=5). Each test case specifies:
- Line 1: n ( 1 ≤ n ≤ 20,000 )
- Line 2: X1 X2… Xn ( 1 ≤ Xi ≤ 100 i=1…. n)
- Line 3: c ( 1 ≤ c≤ 10 )
- Line 4: Y1 Y2… Yc ( 1 ≤ Yi ≤ 100 i=1…. c)
输出
For each test case generate a single line: a single integer that there are several matching points. The matching gene sequence can be partially overlapped
样例输入 Copy
1
6
1 8 5 7 9 10
3
4 6 7
样例输出 Copy
2
#include<bits/stdc++.h>
using namespace std;
int T,n,c;
int a[20001],b[11],cc[11];
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
scanf("%d",&n);
for(int i=0;i!=n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&c);
for(int i=0;i!=c;i++)
{
scanf("%d",&b[i]);
}
sort(b,b+c);
for(int i=c-1;i>=0;i--)
{
b[i]-=b[0];
}
int ans=0;
for(int i=0;i<=n-c;i++)
{
for(int j=0;j!=c;j++)
{
cc[j]=a[i+j];
}
sort(cc,cc+c);
for(int j=c-1;j>=0;j--)
{
cc[j]-=cc[0];
}
int j=1;
for(j=1;j!=c;j++)
{
if(cc[j]!=b[j])break;
}
if(j==c)ans++;
}
printf("%d\n",ans);
}
}
return 0;
} 2310: Checkpoints
时间限制: 3 Sec 内存限制: 128 MB
提交: 21 解决: 18
[提交] [状态] [讨论版] [命题人:外部导入]
题目描述
As a landlocked country in central and southern Africa , the political situation has been relatively stable since the implementation of multi-party elections in ZBA in 1991. But the ZBA parliament passed the 90 day emergency order issued by the president on 11 days of local time . The tension is that the patriotic team led by the government troops and NPG leaders founded by aborigines started, in addition to the unlawful insurgents of illegal militants.
Chinese peacekeepers are going to the town of Kerver to seek Chinese foreign aid engineers.
The military map shows that there are many checkpoints in the war zone. It can be modeled as a directed graph: nodes represent checkpoints , and edges represents the roads. The goal is that the less peacekeepers pass the checkpoints, the safer it will be.
输入
The first line of the input contains one integer T, which is the number of test cases (1<=T<=5). Each test case specifies:
* Line 1: N M A B (2 ≤ N ≤ 100)
N and M denote the number of nodes and edges in the directed graph respectively. The checkpoints are labeled 1, 2, …, N, where chinese peacekeepers at node A and foreign aid engineers at node B.
*Line 2~m+1: Xi Yi (i=1, …., M)
followed by M lines containing two integers Xi and Yi (1 ≤ Xi, Yi ≤ N), denoting that there is a directed edge from node Xi to node Yi in the network.
输出
For each test case generate a single line: a single integer that the minimum number of checkpoints . If a checkpoint is passed on the way back and forth , it will be counted only once.
样例输入 Copy
1
6 10 1 5
1 2
2 1
2 3
3 5
5 4
4 2
1 6
6 5
5 3
3 2
样例输出 Copy
2
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=101;
int T,n,m,a,b,s,e;
int map1[maxn][maxn];
vector<set<int> > v;
bool flag=0;
bool vis[maxn];
int pre[maxn];
int ans=inf;
void dfs_s(int ss)
{
if(ss==b)
{
set<int> s1;
int t=ss;
while(t)
{
s1.insert(t);
t=pre[t];
}
v.push_back(s1);
}
for(int i=1;i<=n;i++)
{
if(!vis[i]&&map1[ss][i])
{
vis[i]=1;
dfs_s(i);
vis[i]=0;
}
}
}
void dfs_e(int ss)
{
if(ss==a)
{
set<int> s1,s2;
int t=ss;
while(t)
{
s1.insert(t);
t=pre[t];
}
for(int i=0;i!=v.size();i++)
{
s2=v[i];
set_union(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s2,s2.begin()));
ans=min(int(s2.size()),ans);
}
}
for(int i=1;i<=n;i++)
{
if(!vis[i]&&map1[ss][i])
{
vis[i]=1;
dfs_e(i);
vis[i]=0;
}
}
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
ans=inf;
memset(map1,0,sizeof(map1));
scanf("%d %d %d %d",&n,&m,&a,&b);
ans=inf;
for(int i=0;i!=m;i++)
{
scanf("%d %d",&s,&e);
map1[s][e]++;
}
flag=0;
memset(vis,0,sizeof(vis));
memset(pre,0,sizeof(pre));
dfs_s(a);
flag=1;
memset(pre,0,sizeof(pre));
memset(vis,0,sizeof(vis));
dfs_e(b);
printf("%d\n",ans);
}
}
return 0;
} 2311: Attack City and Capture Territory
时间限制: 3 Sec 内存限制: 128 MB
提交: 25 解决: 17
[提交] [状态] [讨论版] [命题人:外部导入]
题目描述
The Three Kingdoms period was a relatively famous period in the history of China. From the Battle of Chibi (AD 211) to the reunification of China in the Western Jin Dynasty(AD 280). During the period, Cao’s Wei State, Liu’s Shu State, and Sun’s Wu Guo’s Three Kingdoms stood together. Therefore, it was called the Three Kingdoms period.
In the last years of the Eastern Han Dynasty, Dong_ Z specialized in power , the coalition forces of the world’s princes crusade against each other. Among them, Liu_B and Sun_Q, who are school students, also participated in the crusade.
In AD 215 , Liu_B and Sun_Q simultaneously attacked JingZhou and directly threatened Dong Z’s city. There were N firepower points on the high wall, each fire point with different s trength Xi . Liu_B and Sun_Q looked at the high walls and the strong gates, they did not attack the city traightaway. They negotiate to attack firepower point alternately. Who breaks through the last firepower point, he will win the city.
Because of limited weaponry, weapons of each side can only attack one firepower at a time. But they can control whether completely destroy this firepower point or weaken the strength of firepower point.
Liu_B has a strong think-tank. After calculation, he finds out who will attack first , who will more likely win the city .
输入
The first line of the input contains one integer T, which is the number of test cases (1<=T<=10). Each test case specifies:
- Line 1: N ( 1 ≤ N ≤ 100 )
- Line 2: X1 X2… Xn ( 1 <= Xi<=1000 i=1…. n)
输出
For each test case , print “Liu_B is sure to win.” Or “Liu_B is not sure to win.” , suppose Liu_B first attacks.
样例输入 Copy
3
2
1 3
2
3 3
5
1 2 3 4 5
样例输出 Copy
Liu_B is sure to win.
Liu_B is not sure to win.
Liu_B is sure to win.
分析：NIM博弈
我们的解题思想是基于下面一个事实：
首先我们计算一下所有数字的异或和。sum
先定义两种状态，一种是能胜利的状态，一种是失败的状态。
如果一个人面临的异或和大小为0 ，那么说明已经没有城市可以打了，对手打下了最后一个城市。
那这个人就输了，定义为N状态。
如果一个人所面临的异或和不是0 ，那么我们一定有方法把，当前的异或和调成0 ，从而丢给对手一个N状态。
怎么丢呢？
假设异或和是 11011
那么一定有一个城市提共了异或和的最高位的那个1
我们只需要找到这个城市，把这个城市的数量减少到 1011就好，这样异或和就为0 了
这样我们处于P状态的对手一直能把P状态调成N状态丢给对手。
N状态的对手不管怎么调都会使N状态变回P状态，
所以面对N状态的对手必输。
#include<bits/stdc++.h>
using namespace std;
string a[2]={"Liu_B is not sure to win.","Liu_B is sure to win."};
int T;
int n,t,sum;
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&T))
{
while(T--)
{
sum=0;
scanf("%d",&n);
for(int i=0;i!=n;i++)
{
scanf("%d",&t);
sum^=t;
}
if(sum==0)
{
cout<<a[0]<<endl;
}
else
{
cout<<a[1]<<endl;
}
}
}
return 0;
}
京公网安备 11010502036488号