A
Problem Description
Alfred 和
Brian是一对好基友，他们在一起度过难熬的光棍节。但是Brian，这个笨蛋，却愚蠢的破坏了这温馨美好的氛围。他竟然弄坏了Alfred
的量角器！而Alfred却急需用这个量角器来完成他的作业。半夜时分，他们无法出门去购买新的量角器。Brian浑然不理会Alfred的气急。“你
看，这里还剩下两块碎片可以使用，用着两块碎片足以画出所有的角度了。”Brian拿着两块残存的碎片说道。Alfred看了看这两块碎片，一块能画出标
准的M度角，而另一块却正好是N度角的残片，不过其他的刻度部分已经损坏，并不能借由刻度来画出其他的角度。但是Alfred很生气，“不，并不是所有的
整数度角都能画出来！”“那么，你说，哪个角度画不出来？”Brian问道。Alfred马上反问道，“那么，你说，哪个角度画得出来？”
Brian一下语塞了，他并不能马上说出哪个角度画不出来。
为了维护他们之间的基情，好于牵蓝线的你出场了，那么到底哪些角度能画出来呢？
PS:可以多次使用两个碎片组合画出其他的角度,如一块40°的碎片和一块30°的碎片可以相加画出70°的角,也可以相减画出10°的角，当然也能画出60°，80°以及其他更多的角度。
不能使用直线辅助,也就是说不能通过70°加直线画出110°来,但是可以使用360°辅助画出290°
Input
一个正整数T(1 ≤ T ≤ 100)，表示有T组数据。
以下每组数据各有一行输入
包含两个正整数N，M（1 ≤ N,M ＜ 180,1 ≤ M + N ＜ 180），分别代表两个碎片所能绘制的角度。
Output
每组数据输出一行，包含所有可以画出的自然数度数(在[1,360)范围内)，每两个之间包含一个空格，最后一个元素后面不包含空格。如果所有角度都能画出，则输出“I'm sorry, Alfred.”(不包括引号，所有标点为英文标点)。
Sample Input
2
1 2
60 90
Sample Output
I'm sorry,Alfred.
30 60 90 120 150 180 210 240 270 300 330
#include
#include
#include
#include
#include
using namespace std;
int gcd(int x,int y)
{
if(y==0) return x;
return gcd(y,x%y);
}
int main( )
{
int i,m,n;
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
int g=gcd(n,m);
g=gcd(g, 360-g);
if(g==1)
printf("I'm sorry,Alfred.\n");
else{
for (i=g;i<360;i+=g){
if(i==g)
printf("%d",i);
else
printf(" %d",i);
}
putchar('\n');
}
}
return 0;
}
B题
Problem Description
Claude和Derrick是一对好基友。
这天，他们在一起玩游戏。可是Claude却什么都不想玩，除了一个合作防守的TD(TD:Tower Deffence，通过建造箭塔等，防御敌人的入侵的一类游戏)。Derrick只好按捺下想独自去Dota的心情配Claude玩TD。
别看Derrick在Dota界也是小有名气，碰上这类TD游戏却费尽了他的头脑也玩不好。Claude并没有对多次失败而恼火，但Derrick很尴
尬。每次看到自己拖了Claude的后腿，心中就颇为不甘。以前带Claude玩Dota的时候，嘲笑Claude送钱成为ATM的情景浮上眼前，这让他
更加的恼羞成怒了。
在一旁静静看着的你，决定为这段基情做出一些贡献，好让二人身上的蓝线不会就此掉落，你决定帮助Derrick寻找游戏的技巧。
Derrick的问题在于他需要知道他的箭塔和Claude的箭塔总共射程覆盖区域的大小。之后他就能通过这个面积的大小来得到最佳策略。他已知了所有箭塔
PS:攻击范围不同于普通的圆形攻击范围，为与箭塔的横纵坐标差的绝对值都不超过射程的所有点。
即: 第i个箭塔的攻击范围为点集{(x,y)| |x-xi|<=ri&&|y-yi|<=ri)}
(xi,yi,ri为第i个箭塔的x坐标,y坐标和射程)
Input
一个正整数T(1 ≤ T ≤ 100)，表示有T组数据
以下每组数据第一行包含一个整数N(1 ≤ N ≤ 1000)，表示他们俩共建造了N个箭塔。保证不会有三个箭塔能攻击到同一个点。
接下来N行，每行包含三个整数，为xi，yi，ri，分别表示第i个箭塔的x坐标，y坐标和射程(-100000≤xi,yi≤100000，1≤ ri ≤1000)
Output
每组数据输出一行，包含一个正整数，表示所有箭塔的总共射程覆盖区域面积的大小
Sample Input
2
1
0 0 1
2
1 1 1
2 2 1
Sample Output
4
7
#include
#include
#include
#include
#include
using namespace std;
int tow[2000][4];
//因为三塔不重叠，算法简单了很多，如果重叠呢，沿X轴切割？
int overlap(int i, int j)
{
if(tow[i][1]<=tow[j][0]||tow[i][0]>=tow[j][1]||tow[i][3]<=tow[j][2]||tow[i][2]>=tow[j][3])
return 0;
int x[4]={tow[i][0],tow[i][1],tow[j][0],tow[j][1]};
sort(x,x+4);
int y[4]={tow[i][2],tow[i][3],tow[j][2],tow[j][3]};
sort(y,y+4);
return (x[2]-x[1])*(y[2]-y[1]);
}
int main( )
{
int i,j,n;
int cas;
scanf("%d",&cas);
while(cas--){
int area=0;
scanf("%d",&n);
for(i=0;i int x,y,r;
scanf("%d%d%d",&x,&y,&r);
area+=4*r*r;
tow[i][0]=x-r;
tow[i][1]=x+r;
tow[i][2]=y-r;
tow[i][3]=y+r;
}
for(i=0;i for(j=i+1;j area-=overlap(i,j);
printf("%d\n",area);
}
return 0;
}
C题
Problem Description
Gilbert 和 Herbert是一对好基友。
这天，马上就要交的大量作业摆在Gilbert眼前。Herbert虽然自由自在，但是为了
Baseship，他也无法一个人去玩。Gilbert的作业虽然难不倒他，但是过于繁琐的计算过程耗费了大量的时间。而Herbert对此却又一窍不
通，帮不上一丁点忙。Herbert也是急的抓耳挠腮却又无计可施。
旁边的你看着Herbert的着急样子，也深受他们之间的Baseship的感动，你决定伸出援手写一个程序来解决Gilbert的作业，为他们牢固的蓝线在加上一道保障。
Gilbert的作业如下：
我们定义，用大写字母’A’~’Z’表示一个简单命题。一个复合命题分为三类分别形如A->B,C&&D,F||G。每一个命题的值为‘真’或‘假’。简单命题的值不确定。复合命题的值由其表达式和其中包含的简单命题的值确定对应情况见下图。
![]()
问题是，给出K个复合命题作为“前提条件”（即所有简单命题的取值需要满足使得这些命题为真），问一个指定的符合命题的值的情况，如果在所有满足“前提条件”为真的情况下都为真，则称之为“恒定为真”。
一个正整数T(1≤T≤100)，表示有T组数据
以下每组数据第一行包含一个整数K(1≤K≤5)，接下来K+1行，每行包含一个字符串，字符
串包含四个字符，第一个和第四个字符为’A’~’Z’其中之一（由于ET带着UFO飞走了，所以只有21个字母(即不包
括’E’,’T’,’U’,’F’,’O’五个字母)），第二，三个字符为以下三种组合之一”->”，”&&”，”||”，全部符
号为英文符号。
前K个字符串表示前提条件，最后一个字符串表示被询问的复合命题。
Output
每组数据输出一行，如果“恒定为真”，则输出 “Yes”，反之则输出”No”
Sample Input
2
1
A&&B
A||B
2
A||B
C||C
D&&F
Sample Output
Yes
No
//错误检讨，写错YES和NO
#include
#include
#include
#include
#include
using namespace std;
char s[10][10];
int n;
bool vis[300];
bool cv[300];
char ch[300];
int pre,post;
//check predict s[i]
bool check(int i)
{
if(s[i][1]=='&'&&s[i][2]=='&')
return cv[s[i][0]]&&cv[s[i][3]];
else if(s[i][1]=='|'&&s[i][2]=='|')
return cv[s[i][0]]||cv[s[i][3]];
else
return !(cv[s[i][0]]&&(!cv[s[i][3]]));
}
void dfs(int k)
{
if(k==0){
int i;
for(i=0;i if(!check(i))
break;
}
if(i==n){
pre++;//pre表示所有前置命题为真
if(check(n))//post表示被询问的复合命题
post++;
}
return;
}
cv[ch[k]]=false;
dfs(k-1);
cv[ch[k]]=true;
dfs(k-1);
}
int main( )
{
int i;
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
pre=post=0;
memset(vis,0,sizeof(vis));
memset(ch,0,sizeof(ch));
memset(cv,0,sizeof(cv));
for(i=0;i<=n;i++){
scanf("%s",s[i]);
vis[s[i][0]]=true;
vis[s[i][3]]=true;
}
//枚举所有参与的变量
int cnt=1;
for(i='A';i<='Z';i++)
if(vis[i])
ch[cnt++]=i;
dfs(cnt-1);
if(pre&&pre==post)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
/*
7
2
A->B
B&&C
C||D
5
A&&B
C&&D
G&&H
A->B
C->D
A->G
5
A&&B
C&&D
G&&H
A->B
C->D
A&&G
5
A&&B
C&&D
G&&H
A->B
C->D
I&&G
2
A->B
B&&C
A||B
2
A->B
B->C
A||B
1
A||B
A->B
1
A->B
A||B
1
A&&B
A||B
2
A||B
C||C
D&&F
*/
D题
Problem Description
Issac 和 Jeremy 是一对好基友，这天是光棍节。所以，Issac决定对Jeremy提了一个有意思的问题，光棍数。
定义光棍数如下
对于一个正整数K，如果存在一个非负整数X，使得K=111*X+1或K=11*X+11；
则称K是一个光棍数。
显然，最小的光棍数为1。将所有光棍数从小到大排列，“1”被称为第一个光棍数。那么第N个光棍数是多少呢？
Hint
因为int的数据范围实在是太小了，在这道题里面会超界的哟。
所以同学们请使用 __int64 代替吧。
输入输出的时候，相应的，要用%I64d来代替原有的%d的哟。
Input
一个正整数T(1 ≤ T ≤ 100)，表示有T组数据
以下每组数据包含一个正整数N(1≤N≤10^9)
Output
Sample Input
4
1
11
111
1111
Sample Output
1
110
1111
11209
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef __int64 LL;
__int64 find(LL low, LL high, __int64 n)
{
LL mid=(low+high)/2;
__int64 total=mid/11+(mid-1)/111+1;
//能同时满足两个方程K=111*X+1或K=11*X+11；的通解为111*(10+11t)+1=1111+11*1111t (t=0,1,2...)
__int64 t=mid-1111;
if(t>=0)
total-=t/(11*111)+1;
if(total>n)
return find(low,mid-1,n);
else if(total return find(mid+1,high,n);
else{
__int64 i;
for(i=mid; ;i--)
if((i-1)%111==0 || (i-11)%11==0)
break;
return i;
}
}
int main( )
{
__int64 n;
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%I64d", &n);
__int64 v=(n-1)*11+11;
printf("%I64d\n",find(1,v,n));
}
return 0;
}
E题
Problem Description
Kerwin 和 Lester是一对好Basefriend，在“六一光棍节”这天，他们漫步校园，来到了一个石子堆前。
Kerwin决定戏
耍一下Lester，以便让他为自己的晚饭买单，以解救自己羞涩的钱包。Kerwin来到石子堆前，抓了一把石子，分成了几堆，说道：“Lester，咱
们来玩个游戏吧。”“什么游戏？”“你看，这里有几堆石子，我们轮流从其中一堆拿走一个或者两个石子，由我先取，如果谁取走了最后一颗石子谁输。嗯，输一
局请对方一顿饭。”Lester听完规则，微微一下“好啊！”Kerwin虽然对于Lester的微笑心下有些底气不足，但是也没法多想。
果不其然，几局过后，Kerwin输得一塌糊涂，已经欠下了一个月的晚饭了。Kerwin心下很是气恼。Lester一看Kerwin的恼怒样，决定再刺激他一下“最后一局来把大的吧，你赢了，咱俩扯平，反之，你多输半个月的。怎么样，划算吧？”
一直在关注着他们俩的你，在一旁也看不下去了。在Kerwin做出决定前，你发现了Lester获胜的原因。你告诉了Kerwin最佳策略。
Kerwin并不愚蠢，知晓最佳策略后，他立即知道了最佳策略下，游戏的结果。
那么他是否应该答应Lester的挑战呢？
Input
一个正整数T(1 ≤ T ≤ 100)，表示有T组数据。
以下每组数据各有两行输入
第一行包含两个正整数N（1 ≤ N ≤ 100000），表示有N堆石子。
第二行包含N个正整数Ai(1 ≤ i ≤ N, 1 ≤ Ai ≤ 100000)表示第i堆石子有Ai个石子。
Output
每组数据输出一行，包含一个字符串，当Kerwin有必胜策略时，输出“Yes”，当Kerwin必败时，输出“No”。（在Lester采取最佳策略的情况下）
Sample Input
2
1
1
2
1 2
Sample Output
No
Yes
来自王的代码
思路：每堆石子mod3，统计1的个数a，2的个数b。然后推出赢的条件即可。
#include
int main()
{
int t,n,cnt,m;
int a,b;
scanf("%d",&t);
while(t--)
{
a=0;
b=0;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
if(m%3==1) a++;
if(m%3==2) b++;
}
if( (b==0&&a%2==0)||
b%2==1||(b>1&&b%2==0&&a%2==1)) printf("Yes\n");
else
printf("No\n");
}
return 0;
}
F
Problem Description
Matthew and Nerd are “base friends”. In the Single's Day, the boring time drove the two guys to look for entertainment.
Nerd is a real geek, Matthew is another one, so they began to play a geek's game.
At
first Nerd write a '0' or '1' on the page, and then Matthew give
another '0' or '1', they took turns to do the same thing. However, "11"
is too depressing for them, so if someone wrote '1', the next one must
follow by '0'.
Nerd was curious about how many results the game would
generate, he was going to solve it while Matthew announced that the
answer had being in his mind."I have known it too!!"The vanity made
Nerd's mouth out of control." Okay, let us write our answers, and have a
comparation, can you?”Matthew said with confidence, but Nerd didn't
know actually, so -_-0....
Just as vocabulary is gap between lovers,
so how can two geeks with different intelligence tie to each other! Can
you give Nerd a hand to keep their “Baseship”?
Input
The first line give an integer T (1 <= T <= 100000),means there
are T test cases, each test case contain an integer K (1 <= k <=
100000),representing the steps of game(you can see write a number as a
step).
Output
For each test case, print one line containing the number of different
results after K steps. For the number is too big, you need to let the
result % 9997.
Sample Input
3
1
2
20
Sample Output
2
3
7714
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int main( )
{
int n;
int dp[2];
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
dp[0]=1;
dp[1]=1;
int i=1;
while(i++ int old[2]={dp[0],dp[1]};
dp[0]=(old[0]+old[1])% 9997;
dp[1]=old[0]% 9997;
}
printf("%d\n",(dp[0]+dp[1])% 9997);
}
return 0;
}
G题
Problem Description
Payne和Quincy是一对好Basefriend，即使在“六一光棍节”这天，寂寞无聊的Payne决定调戏一下Quincy。
他在一张纸上写下了一串数字，然后来到Quincy面前。
“嗨，Quincy，我看你也挺无聊的，来验证一下你的智商吧。”
“噢，Payne，你又有什么鬼主意了？”
“嘿，听一听吧，会很有趣的！”
“嗯，那你说吧。”
“哈，
听着，你看这里有一串数。我们从中取一段连续的数字，比如你看这的1357902468147258369，我们从中取出一段长度为7的子串，可以是
5790246，或者是0246814。这样我们就得到了一些新的数。然后，让我们看看长度为7的所有子串所表示的数里面，共有多少个数是9的倍数。”
“哼，多简单的游戏啊。小孩都会算。”
“呵，那咱俩来试试？我写一个数，你来告诉我答案？”
Input
一个正整数T(1 ≤ T ≤ 100)，表示有T组数据。
以下每组数据各有两行输入
第一行包含两个正整数N，M（1 ≤ N ≤ 10^6,1 ≤ M ≤ 10^3），表示母串长度为N，子串长度为M。
第二行包含一个大数，大数按十进制表示，共有N位。
Output
每组数据输出一行，包含一个数，表示母串中所有长度为M的子串中，为9的倍数的个数
Sample Input
2
3 2
181
5 3
18171
Sample Output
2
1
#include
#include
#include
#include
#include
using namespace std;
//题意并不清晰，重复的子串有效
//一开始开小了数组，晕
char s[2000000];
int dp[2000000];
int main( )
{
int i,m,n;
int cas;
scanf("%d",&cas);
while(cas--){
int cnt=0;
scanf("%d%d",&n,&m);
scanf("%s", s);
if(m>n){
printf("%d\n",0); continue;
}
dp[m-1]=0;
for(i=0;i dp[m-1]+=s[i]-'0';
if(dp[m-1]%9==0)
cnt++;
for(i=m;i dp[i]=dp[i-1]+s[i]-s[i-m];
if(dp[i]%9==0)
cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
H题
这个题目坑爹，K个任务一开始指定后，不能变了，哪怕是完成了也不能补充
#include
#include
#include
#include
#include
#include
using namespace std;
//题意不是很清晰，首先任务全部同时启动，
//其次，当有任务完成时，空闲的带宽应该均分给剩下的任务
double v[100000];
int main( )
{
int i;
double min;
int cas;
scanf("%d",&cas);
while(cas--){
int n,k;
double w;
scanf("%d%lf%d",&n,&w,&k);
for(i=0;i scanf("%lf",&v[i]);
}
sort(v,v+n);
for(i=0;i v[i]*=2;
sort(v,v+n);
min=v[0]*n/w/2.0;
for(i=1;i min+=(v[i]-v[i-1])*(n-i)/w/2.0;
//printf("%d %f\n",(int)ceil(min),min);
printf("%d\n",(int)ceil(min));
}
return 0;
}
J
Problem Description
输入一个大数,删除其中连续的奇数个1后输出
Input
一个正整数T(1 ≤ T ≤ 100)，表示有T组数据。
以下每组数据各有一行输入
包含一个字符串,字符串的长度len(1<=len<=10000),字符串仅由\'0\'~\'9\'十个数字组成
Output
每组数据输出一行,为一个字符串
为输入的字符串中删除掉连续的奇数个\'1\'后的结果,如果没有数字输出空行
Sample Input
4
111
313113
41114
11
Sample Output
33113
44
11
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int cnt;
void filter(char *s, char *t)
{
int i=0,j=0,k;
if(*s==0) return;
while(s[i]&&s[i]!='1')
t[cnt++]=s[i++];
while(s[i+j]=='1')
j++;
if(j%2==0)
for(k=0;k t[cnt++]='1';
filter(s+i+j,t);
}
int main( )
{
char s[20000];
char t[20000];
int cas;
scanf("%d",&cas);
while(cas--){
cnt=0;
scanf("%s",s);
filter(s,t);
t[cnt]=0;
if(cnt==1)
puts("");
else
puts(t);
}
return 0;
}
阅读(1068) | 评论(0) | 转发(0) |
