【2018-ICPC-Pacific-Northwest-Regional-Contest-Div1】

http://codeforces.com/gym/101982

【A-Exams】limit 1 second

【Description】

Your friend and you took a true/false exam of n questions. You know your answers, your friend’s answers, and that your friend got k questions correct. Compute the maximum number of questions you could have gotten correctly.

【Input】

The first line of input contains a single integer k. The second line contains a string of n (1 ≤ n ≤ 1000) characters, the answers you wrote down. Each letter is either a ‘T’ or an ‘F’. The third line contains a string of n characters, the answers your friend wrote down. Each letter

is either a ‘T’ or an ‘F’. The input will satisfy 0 ≤ k ≤ n.

【Output】

Print, on one line, the maximum number of questions you could have gotten correctly.

【题目大意】

你的朋友和你正在进行一场考试,考试n个判断正误问题,答案是T/F.你知道你朋友的答案和你自己的答案。而且你朋友的答案有k个是正确的,计算你可能正确的最大数量。

【输入】

输入第一行一个整数k,第二,三行是两个长度为n 的TF字符串,.分别代表你自己的答案和朋友的答案,保证只有大写的T,或F,且0 ≤ k ≤ n.

【输出】

输出一行一个整数,表示你自己可能答对的最大题数。

【分析】

每道题可分为两种情况,即此道题答案二人是否一致,记答案相同的题目数为S(ame),不同答案的题目数为d(iffer)。为了最大化自己的正确答案数,有一种明显的策略。即朋友答对题的我也答对了,朋友不正确的题的我依然正确。也即优先将朋友答对的k道题分配给答案相同的题目身上.如果k>S,则在二者答案不同的d道题中有k-S道是朋友对的而我是错的,Ans=S+(d-(k-S)).如果k则在二者答案相同的S道题中有S-k道是两个人都答错了,剩下的d道不同的题可认为我都答对了,故Ans=k+d.如果k==S,则可以认为我全部答对了,即ans=S+d.又一共有n道题,故d=n-S,带回得:Ans=S+(n-S-(k-S))=S+(n-S-k+S)=S+n-k,(k>S);Ans=k+d=k+n-S,(k再整理得到Ans=n-abs(k-s);

【代码】

过于简单,不做展示

=================================================================

【C-Contest Setting】limit 1 second

【Description】

A group of contest writers have written n problems and want to use k of them in an upcoming contest. Each problem has a difficulty level. A contest is valid if all of its k problems have different

difficulty levels. Compute how many distinct valid contests the contest writers can produce. Two contests are distinct if and only if there exists some problem present in one contest but not present in the other. Print the result modulo 998,244,353.

【Input】

The first line of input contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 1000). The next line contains n space-separated integers representing the difficulty levels. The difficulty levels are between 1 and 10^9 (inclusive).

【Output】

Print the number of distinct contests possible, modulo 998,244,353.

=================================================================

【题目大意】

一个竞赛组织者准备了n道题,并将选择其中k道来组一次比赛。每道题有一个难度系数,且比赛选取的k道题两两之间难度系数不同。计算有多少种不同的可行比赛方案。如果存在某道题在A方案中出现而B方案中没有出现则认为A,B是两种不同的方案,计算答案后mod 998,244,353.

【输入】

第一行两个整数n, k(1 ≤ k ≤ n ≤ 1000).下一行包含n个整数,代表编号从1到n的题目难度系数。难度系数值<=1e9

=================================================================

【分析】

由于不同的题目之间可能难度系数相同,而选取的题目组合之间难度系数得不同,故先排序处理,将相同难度的题目归为同一类。设难度系数一开始存储在num[]中,排序后统计,放入ite[]中,ite[i]表示第i类题的题目数量。

下面是dp思路。由于答案只和题目数有关,设f[i][j]表示前i类题选取j题的方案数。

明显有f[1][1]=ite[1],在第一类题中选一题的方案数就是第一类题的数量。当i>=2时,如果j>i则为0:因为同一类题中最多选取一道,题目数不可能超过类数。当j<=i时,f[i][j]=f[i-1][j-1]*ite[i]+f[i-1][j];即前i-1类选取j-1道的方案情况下,任选第j类的任意一道都可以。当前i-1类选取了j道的方案情况下,第j类就不能再选取了。最后答案保存在f[n][k]中。

=================================================================

【代码】

scanf("%d %d",&n,&k);

for(int i=1;i<=n;i++) scanf("%I64d",&num[i]);

sort(num+1,num+n+1);

int newn=0;

for(int i=1;i<=n;i++){

   if(num[i]!=num[i-1]) ++newn;

   ite[newn]++;

}

n=newn;

f[0][0]=1;f[1][1]=ite[1];

for(int i=2;i<=n;i++){

   f[i][1]=f[i-1][1]+ite[i];

   for(int j=2;j<=k;j++){

       if(j>i) f[i][j]=0;

       else{

          f[i][j]=f[i-1][j-1]*ite[i]+f[i-1][j];

          f[i][j]%=998244353;

       }

   }

}

cout<<f[n][k]8244353;

=================================================================

【Problem G-Goat on a rope】limit 1 second

【Description】

You have a house, which you model as an axis-aligned rectangle with corners at (x1; y1) and (x2; y2). You also have a goat, which you want to tie to a fence post located at (x; y), with a rope of length

l. The goat can reach anywhere within a distance l from the fence post. Find the largest value of l so that the goat cannot reach your house.

【Input】

Input consists of a single line with six space-separated integers x, y, x1, y1, x2, and y2. All the values are guaranteed to be between −1000 and 1000 (inclusive).It is guaranteed that x1 < y1 and x2 < y2, and that (x; y) lies strictly outside the axis-aligned

rectangle with corners at (x1; y1) and (x2; y2).

【Output】

Print, on one line, the maximum value of l, rounded and displayed to exactly three decimal places.

=================================================================

【题目大意】

你有一个房子,是与坐标轴平行的矩形,从(x1,y1)到(x2,y2)。还有一只山羊,用长度为l的绳栓在处于(x, y)的栅栏上,现在计算出最大绳长L,同时山羊不会碰到房子内部。

【分析】

不用说,就几个判断而已的水题

=================================================================

【Problem H - Repeating Goldbachs】 limit 1 second

【Description】

The Goldbach Conjecture states that any even number x ≥ 4 can be expressed as the sum of two primes. It can be verified that the conjecture is true for all x ≤ 10^6. Define a Goldbach step as taking x (4 ≤ x ≤ 10^6), finding primes p and q (with p ≤ q) that sum to x, and replacing x with q − p. If there are multiple pairs of primes which sum to x, we take the pair with the largest difference. That difference must be even and less than x. Therefore, we can repeat more Goldbach steps, until we can reach a number less than 4. Given x, find how many Goldbach steps it takes until reaching a number less than 4.

【Input】

The input will consist of a single integer x (4 ≤ x ≤ 10^6).

【Output】

Print, on a single line, the number of Goldbach steps it takes to reach a number less than 4.

=================================================================

【题目大意】

哥德巴赫猜想说:任何≥4的偶数可以表示为两个素数的和。当对所有x≤10^6时可以证明猜想正确。定义一个“哥德巴赫步骤”:是取一个数字x,找到质数p, q且p≤q ,p + q=x,然后x变为q-p. 如果存在多个p,q满足条件,选择差值最大的一组。而且明显的有q-p一定是小于x的偶数。重复若干次“哥德巴赫步骤”,直到x小于4.现在给定x,找到x变成小于4要多少个“哥德巴赫步骤”。

=================================================================

【分析】

纯粹的模拟题。先筛法求出1~10^6的质数,然后模拟这个过程即可。

=================================================================

define maxn 100010

const int Maxm=1000000;

int cnt,pri[maxn];bool ispri[Maxm+10];

void pre()

{

cnt=0;memset(ispri,false,sizeof(ispri));

ispri[0]=ispri[1]=true;

for (int i=2;i<=Maxm;i++)

{

   if (!ispri[i]) pri[++cnt]=i;

   for (int j=1;j<=cnt && i*pri[j]<=Maxm;j++)

   {

       ispri[i*pri[j]]=true;

       if (i%pri[j]==0) break;

   }

}

}

int main()

{

int x,ans,l,r,t;

pre();ans=0;

scanf("%d",&x);

while (x>=4)

{

   l=1;r=cnt;t=1;

   while (l<=r)

   {

       int mid=(l+r)>>1;

       if (x>=pri[mid]) {t=mid;l=mid+1;}

       else r=mid-1;

   }

   while (t && ispri[x-pri[t]]) t--;

   x=pri[t]-(x-pri[t]);ans++;

}

printf("%d\n",ans);

return 0;

}

=================================================================

【Problem L - Liar】 limit 1 second

【Description】

There are n people in a circle, numbered from 1 to n, each of whom always tells the truth or always lies. Each person i makes a claim of the form:” the number of truth-tellers in this circle is between ai and bi, inclusive.” Compute the maximum number of people who could be telling the truth.

【Input】

The first line contains a single integer n (1 ≤ n ≤ 10^3). Each of the next n lines contains two space-separated integers ai and bi (0 ≤ ai ≤ bi ≤ n).

【Output】

Print, on a single line, the maximum number of people who could be telling the truth. If the given set of statements is inconsistent, print -1 instead.

=================================================================

【题目大意】

N个人围坐一圈,编号从1到n。每个人的陈述总是真话或假话。每个人都会陈述以下格式的内容:“我们当中说真话的人数在ai到bi之间,包含ai和bi“。现在计算最大可能的说真话人数。

=================================================================

【分析】

签到题,枚举说真话的人数为i,依次验证每个人说话的真假。这样O(n2),但由于n≤103,也不会超时。

=================================================================

define maxn 1100

struct node{

    int l,r;

}a[maxn];

int main(){

    int n,i,cnt,j,ans=-1;

    scanf("%d",&n);

    for (i=1;i<=n;i++)    scanf("%d%d",&a[i].l,&a[i].r);

    for (i=n;i>=0;i--)  {

       cnt=0;

       for (j=1;j<=n;j++) if(a[j].l<=i&&i<=a[j].r) cnt++;

       if (cnt==i) {ans=i;break;}

    }

    printf("%d\n",ans);

    return 0;

}

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,099评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,828评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,540评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,848评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,971评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,132评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,193评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,934评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,376评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,687评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,846评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,537评论 4 335
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,175评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,887评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,134评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,674评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,741评论 2 351

推荐阅读更多精彩内容