上午
上午好像就做了点题
讲个笑话，一次AC（其实一共交了35次
子集和问题（提交21次
【问题描述】
子集和问题的一个实例为〈S,t〉。其中，S={ x1， x2，…， xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得子集S1和等于c。
【编程任务】
对于给定的正整数的集合S={ x1， x2，…， xn}和正整数c，编程计算S 的一个子集S1，使得子集S1和等于c。
【输入格式】
第1行有2个正整数n和c，n表示S的个数，c是子集和的目标值。接下来的1行中，有n个正整数，表示集合S中的元素。
【输出格式】将子集和问题的解输出。当问题无解时，输出“No Solution!”。【输入样例】
5 10
2 2 6 5 4
【输出样例】
2 2 6请认真断句（”{子集和问题}的解”
笑死TLE和WA交替出现（为什么题目描述里面没有数据范围。。。
思路倒挺简单，但是后三个点TLE得73分
发下来题解之后发现
预处理非常重要
当求到某一位时，目前的子集和加上后面所有元素都小于目标值时，显然已经错了
那么就预处理出i后面的所有值的和
即
1
2
3for(int i = n-1;i>=0;i--){
D[i] = D[i+1]+A[i];
}这么一剪，然后就过了（
工作分配问题（交了2次
【问题描述】
设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为$c_{ij}$ 。试设计一个算法，为每一个人都 分配一件不同的工作，并使总费用达到最小。
设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。【输入格式】
第一行有1个正整数n (1≤n≤20)。接下来的n行，每行n个数，第i行表 示第i个人各项工作费用
【输出格式】
计算出的最小总费
【样例输入】
3
4 2 5
2 3 6
3 4 5
【样例输出】
9这好像就是昨天的题…
哦我没放博客里啊那没事了第一次80分TLE，忘剪枝了（
剪完就AC了
装载问题（交了3次
有一批共n个集装箱要装上1艘载重量分别为$c$的轮船，其中集装箱i的重量是$w_i$，且不能超。
这个其实可以寻找小于c的最大值（
字符序列
【问题描述】
从三个元素的集合[A,B,C]中选取元素生成一个N 个字符组成的序列，使得没有两个相邻的子序列（子序列长度＝2）相同，例：N＝5 时ABCBA 是合格的，而序列ABCBC 与ABABC 是不合格的，因为其中子序列BC，AB 是相同的。
输入N（1<=N<=12）,求出满足条件的N 个字符的所有序列和其总数。【输入样例】
4
【输出样例】
72如题，两个相邻的子序列，相邻就行，不需要再多判断了
两个字，让我多花了两小时1
2
3
4
5
6bool check(int l){
for(int i = 0;i<l-3;i++){
if(A[i] == A[i+2] && A[i+1] == A[i+3]) return true;
}
return false;
}
数据结构—栈
板子
1 | //不过好像有STL专门用来做栈这个数据结构的 |
括号序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
char stack_[2000050];
char ss[200050];
//对栈的操作：入栈、出栈、访问栈顶元素
int p = 0;
void push(char s){stack_[p++] = s;}
void pop(){p--;}
char top(){return stack_[p-1];}
//判断是不是左括号
bool isL(char c){return (c == '(' || c == '[' || c == '{' || c == '<');}
//判断是否匹配
bool cmp(char c,char cc){
switch(c){
case '(':{return cc == ')';break;}
case '{':{return cc == '}';break;}
case '[':{return cc == ']';break;}
case '<':{return cc == '>';break;}
}
}
void f(){
//重置指针（伪
p = 0;
scanf("%s",ss);
for(int i = 0;i<strlen(ss);i++){
char c = ss[i];
//是左括号就入栈
if(isL(c)) push(c);
else{
//右括号与栈顶的左括号匹配就弹出栈顶括号
//下溢就结束
if(cmp(top(),c) && p != 0){
pop();
}else{
printf("FALSE\n");
return;
}
}
}
//判断是否还有剩余的左括号
printf("%s",p?"FALSE\n":"TRUE\n");
}
int main(){
int n;
scanf("%d",&n);
for(int i = 0;i<n;i++){
f();
}
}-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
int stack_[500];
int p = 0;
void push(int a){stack_[p++] = a;}
void pop(){p--;}
int top(){return stack_[p-1];}
int main(){
char s[50];
int len = 0;
char c;
while(true){
scanf("%c",&c);
if(c == '@') break;
//读入数据，
if(c == '.'){
int t = 0;
int len = 0;
for(int i = 0;i<len;i++){
t += (pow(10,len-i-1) * (s[i]-'0'));
}
push(t);
}else{
if(isdigit(c)) s[len++] = c;
else{
int a1 = top();pop();
int a2 = top();pop();
switch(c){
case '+':{push(a1+a2);break;}
case '-':{push(a2-a1);break;}
case '*':{push(a1*a2);break;}
case '/':{push(a2/a1);break;}
}
}
}
}
printf("%d ",stack_[0]);
return 0;
}