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;
}