理解题意很重要，思维好题，spj：答案多个，任意个就判对
问题 B: 求和
时间限制: 1 Sec 内存限制: 128 MB Special Judge
[提交] [状态]
题目描述
考虑自然数1到N，在这N个数之前添加“+”或“-”，然后将N数相加得到和S（0 < S≤100000）。求可以获得和S最小的自然数N。
输入
仅包含1行，一个整数，表示和S。
输出
第1行一个正整数，表示获得和S的最小自然数N。
接下来若干行，每行一个整数，表示添加了“-”的自然数（添加了“+”的自然数不输出），按从小到大的顺序输出。注意：添加“+”或“-”的方案可能不唯一。
样例输入 Copy
12
样例输出 Copy
7
1
7
提示
因为12=-1+2+3+4+5+6-7，故获得和12的最小自然数是7，在1到7的7个自然数中，在1和7之前添加了“-”。
10%的数据保证0 < S≤ 20
30%的数据保证0 < S≤ 150
60%的数据保证0 < S≤ 50000
100%的数据保证0 < S≤ 100000
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,sum=0;
scanf("%d",&n);
for(int i=1;;i++)
{
sum+=i;
if(sum==n)
{
printf("%d",i); return 0;
}
if(sum>n&&(sum-n)%2==0)//+1和-1差2
{
printf("%d\n",i);
break;
}
}
if((sum-n)/2==1)
{
printf("1\n");
}
else if((sum-n)/2!=1)
{
if((sum-n)/2==2) printf("2\n");
else
{
printf("1\n");
printf("%d\n",(sum-n)/2-1);
}
}
return 0;
}
问题 N: Block Game
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
Farmer John is trying to teach his cows to read by giving them a set of N spelling boards typically used with preschoolers (1≤N≤100). Each board has a word and an image on each side. For example, one side might have the word 'cat' along with a picture of a cat, and the other side might have the word 'dog' along with a picture of a dog. When the boards are lying on the ground, N words are therefore shown. By flipping over some of the boards, a different set of N words can be exposed.
To help the cows with their spelling, Farmer John wants to fashion a number of wooden blocks, each embossed with a single letter of the alphabet. He wants to make sufficiently many blocks of each letter so that no matter which set of Nwords is exposed on the upward-facing boards, the cows will be able to spell all of these words using the blocks. For example, if N=3 and the words 'box', 'cat', and 'car' were facing upward, the cows would need at least one 'b' block, one 'o' block, one 'x' block, two 'c' blocks, two 'a' blocks, one 't' block, and one 'r' block.
Please help the Farmer John determine the minimum number of blocks for each letter of the alphabet that he needs to provide, so that irrespective of which face of each board is showing, the cows can spell all N visible words.
输入
Line 1 contains the integer N.
The next N lines each contain 2 words separated by a space, giving the two words on opposite sides of a board. Each word is a string of at most 10 lowercase letters.
输出
Please output 26 lines. The first output line should contain a number specifying the number of copies of 'a' blocks needed. The next line should specify the number of 'b' blocks needed, and so on.
样例输入 Copy
3
fox box
dog cat
car bus
样例输出 Copy
2
2
2
1
0
1
1
0
0
0
0
0
0
0
2
0
0
1
1
1
1
0
0
1
0
0
提示
In this example, there are N=3 boards, giving 23=8 possibilities for the set of upward-facing words:
fox dog car
fox dog bus
fox cat car
fox cat bus
box dog car
box dog bus
box cat car
box cat bus
We need enough blocks for each letter of the alphabet so that we can spell all three words, irrespective of which of these eight scenarios occurs.
开始以为这道题是二叉树，，虽然我根本没学过，，但是这个其实是简化版的排列组合啊。。。。只用考虑我每次是加1号的字母数还是2号的。。。。水题。。。
#include<bits/stdc++.h>
using namespace std;
char st1[105],st2[105];
int a[27]={0},b[27]={0};
int A[27];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s %s",st1,st2);
int len1=strlen(st1);
int len2=strlen(st2);
for(int j=0;;j++)
{
if(j>=max(len1,len2))
break;
if(j<len1) a[st1[j]-'a']++;
if(j<len2) b[st2[j]-'a']++;
}
for(int j=0;j<27;j++)
{
A[j]+=max(a[j],b[j]);
a[j]=0;b[j]=0;
}
}
for(int i=0;i<26;i++)
{
printf("%d",A[i]);
if(i!=25) printf("\n");
}
return 0;
}