急!!!2009年南海区青少年信息学奥林匹克竞赛复赛试题(初中组)

Question

第二题 负进制
(negii.pas/cpp)
题目描述：
学习信息学的人都熟悉 2 进制，但有没有人想过 －2进制！那样的数字就不需要符号了！！
2进制从低位到高位－－即从右向左－－的位权是1、2、4、8、16、....。
－2进制的从右向左的位权当然就是1、－2、4、－8、16、....。
－2进制是可以表示任何整数的。如：
1, 110, 111, 100, 101, 11010, 11011, 11000, 11001,...
表示1，2，3，4，5，6，7，8，9,....
而
11, 10, 1101, 1100,1111,...
则表示-1,-2,-3,-4,-5,....
现在给你一个十进制的整数n，请求出它的－2进制数。
数据范围:
-2,000,000,000≤n≤2,000,000,000
输入文件 ngeii.in:
只一行，一个十进制整数 n。
输出文件 negii.out:
一个－2进制数。如果数字不为0，不能有前导0。
样例:
输入
-13
输出
110111
从右向左：
1*1 + 1*-2 + 1*4 + 0*-8 +1*16 + 1*-32 = -13
第三题 比萨
(pizza.pas/cpp)
题目描述：
NH的最大比萨店为即将来临的节日准备了 T 种不同加味的原料，但考虑到NH人的口味和其它一些因素，原料的使用有 N 种限制。
T种不同原料的编号为1..T。一个限制如“5 3”即表示5号和3号加味原料不能同时使用。如此，此时使用三种原料3,5,6的比萨是不允许的。
现在请你帮忙计算在上面条件下，最多可以制作多少不同的比萨（包括不添加任何加味原料的）。
数据范围:
1≤T≤20
1≤N≤52
输入文件 pizza.in:
第一行：两个整数：T 和 N。
下面有N行：每行表示一种限制。每行的第一个整数 Z(1≤Z≤ T)表示这行后面有Z个表示原料编号的整数，这些原料不能同时出现在一个比萨中。
输出文件 pizza.out:
只一行，一个整数表示在上面的限制下最多可以制成多少种不同比萨。
样例:
输入
6 5
1 1
2 4 2
3 3 2 6
1 5
3 3 4 6
答案说明：
无加料；2；
2和3；2和6；
3；3和4；
3和6；4；
4和6；6。
输出10
答案及解析！急急急！！！

Answer 1

bri.cpp
#include <fstream>

using namespace std;

int main()
{
ifstream in("bri.in");
ofstream out("bri.out");
int I, ans = 0;
in >> I;
for (int i = 1; i <= I; i++)
if (I % i == 0) ans += i;
out << ans << "\n";
return 0;
}

negii.pas
var
a:array[1..10000]of integer;
k,i,n:longint;
begin
assign(input,'negii.in'); reset(input);
assign(output,'negii.out'); rewrite(output);
read(n);
k:=0;
repeat
inc(k);
a[k]:=abs(n mod 2);
n:=-trunc((n-a[k])/ 2);
until n=0;
for i:=k downto 1 do write(a[i]);
writeln;
close(output);
end.

pizza.cpp
#include <stdio.h>
int nconstraints, ntoppings;
int check[52][20];
int ncheck[52];
int ndq = 0;
int toppings[20+1];

void count (int n) {
int i, j, match;
if (n == 0) {
for (i = 0; i < nconstraints; i++) {
match = 1;
for (j = 0; j < ncheck[i]; j++)
match &= toppings[ check[i][j] ];
if (match) { ndq++; return; }
}
return;
}
toppings[n] = 1; count(n-1);
toppings[n] = 0; count(n-1);
}

int main () {
FILE *fin, *fout;
int i, j, k;
fin = fopen ("pizza.in", "r");
fout = fopen ("pizza.out", "w");
fscanf (fin, "%d %d", &ntoppings, &nconstraints);
for (i = 0; i < nconstraints; i++) {
fscanf (fin, "%d", &ncheck[i]);
for (j = 0; j < ncheck[i]; j++)
fscanf(fin, "%d", &check[i][j]);
}
count(ntoppings);
fprintf (fout, "%d\n", (1<<ntoppings) - ndq);
return 0;
}

sents.cpp
#include<fstream>

using namespace std;
ifstream fin("sents.in");
ofstream fout("sents.out");

string words[100],s;
int n;
int dp[100];
void dbg()
{
for (int i=0; i<s.size(); i++)
fout<<dp[i]<<" ";
fout<<endl;
}

bool check_( string a, string b)
{
sort(a.begin(), a.end());
sort(b.begin(), b.end());
return a==b;
}

int main()
{
fin >>n;
for (int i=0; i<n; i++) fin >> words[i];
fin >> s;
s="*"+s;
int m=s.size();
for (int i=1; i<=m; i++) dp[i]=123456;

for (int i=1; i<m; i++)
{
for (int j=0; j<n; j++)
{
if (i+words[j].size()-1 >= m ) continue;
if ( ! check_(words[j], s.substr(i,words[j].size()) ) ) continue;
int cc=0;
for (int k=0,ii=i; k<words[j].size(); k++,ii++)
if (words[j][k]!=s[ii] ) cc++;
dp[i+words[j].size()-1] <?= cc + dp[i-1];
}
}
fout << (dp[m-1]==123456 ? -1 : dp[m-1]) <<endl;
//dbg();
return 0;
}本回答被提问者采纳