3月24日 模拟赛题解
此题我用stack做出了负数，至今不知道为什么，代码如下，麻烦知道的各位大神能告知小的一声：
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<cstdlib>
#include<stack>
#include<cmath>
#include<cctype>
using namespace std;
int temp = 0,t1,t2;
int k = 0;
bool flag = 0;
char c;
long long p;
stack<long> num;
stack<char> s;
int main()
{
// freopen("expr.in","r",stdin);
// freopen("expr.out","w",stdout);
while(1)
{
if(flag == 0)
{
scanf("%lld",&p);
num.push(p);
flag = 1;
k++;
}
else{
if(k >= 2)
{
if(s.top() == '*')
{
t1 = num.top();
num.pop();
t2 = num.top();
num.pop();
num.push(t1 * t2);
s.pop();
}
}
c = getchar();
if(c == '\n') break;
s.push(c);
flag = 0;
}
}
while(!s.empty())
{
t1 = num.top();
num.pop();
t2 = num.top();
num.pop();
s.pop();
num.push(t1 + t2);
}
printf("%d",num.top()%10000);
return 0;
}看到网上大佬的做法，瞬间觉得被碾压。
做法其实就是乘积成块，块区相加。
理解了原理后就好写了：
#include<bits/stdc++.h>
using namespace std;
long long num,sum = 0;
long long cj;
char ch = 0,c;
bool over = 0;
int main()
{
while(!over)
{
scanf("%lld",&num);
over = scanf("%c",&c) == 1 ? 0 : 1;
if(ch == 0) cj = num;//一开始单独成块
if(ch == '+') sum = (sum + cj) % 10000,cj = num;//加上块
if(ch == '*') cj = (cj * num) % 10000;//成块
if(over) sum = (sum + cj)%10000;
ch = c;//保存上一字符
}
printf("%lld",sum);
return 0;
}#include<bits/stdc++.h>
#define MAXA 1000005
using namespace std;
bool isFirst;
long long n,MOD;
long long temp[MAXA],T[MAXA],Fenshu[MAXA],ff[MAXA],MAXN;
int main() {
scanf("%lld %lld",&n,&MOD);
for(int i = 1;i <= n;i++)
scanf("%lld",&ff[i]);
temp[1] = T[1] = MAXN = ff[1];
for(int i=2;i<=n;i++) {
temp[i] = max(temp[i - 1] + ff[i],ff[i]);
T[i] = max(MAXN,temp[i]);
MAXN = T[i];
}
Fenshu[1] = T[1];
Fenshu[2] = T[1] + Fenshu[1];
MAXN = Fenshu[2];
isFirst = Fenshu[1] <= Fenshu[2] ? false : true;
for(int i=3;i<=n;i++) {
if(T[i-1] > 0) {
Fenshu[i] = Fenshu[i-1] + T[i-1];
isFirst = Fenshu[i] > Fenshu[1] ? false : true;
if(Fenshu[i] > 10000000000)
Fenshu[i] %= MOD;
}
else
Fenshu[i] = Fenshu[2];
}
if(isFirst)
printf("%lld",Fenshu[1] % MOD);
else
printf("%lld",Fenshu[n] % MOD);
}
#include<bits/stdc++.h>
using namespace std;
bool dis[1001][1001],els[1001];
int to[1001],p,f[1001],b,i[1001],j[1001];
int n,m,a,ans=0;
int main(){
scanf("%d %d",&n,&m);
int tot = n;
for(int y = 0;y < m;y++){
cin >> a;
int o,k,n1 = 0,n2 = 0;
for(int x = 1;x <= a;x++){
cin >> b;
if(x == 1) o = b;
if(x == a) k = b;
f[b] = 1;
}
for(int x = o;x <= k;x++){
if(f[x])i[++n1] = x;
else j[++n2] = x;
}
for(int x = 1;x <= n1;x++){
for(int z = 1;z <= n2;z++){
if(!dis[i[x]][j[z]])to[i[x]]++;
dis[i[x]][j[z]] = 1;
}
}
memset(f,0,sizeof f);
}
while(tot){
ans++;
int w[n],nu = 0;
for(int x = 1;x <= n;x++){
if(!to[x]&&!els[x]){
tot--;
els[x] = 1;
w[++nu] = x;
}
}
for(int x = 1;x <= nu;x++){
for(int y = 1;y <= n;y++){
if(dis[y][w[x]])to[y]--;
}
}
}
printf("%d",ans);
return 0;
}
n支队伍打比赛，每两支队伍恰好比赛一场。平局时各得1分，而有胜负时胜者3分，负者0分。
假设三支队伍得分分别为3, 3, 3，则可能有两种情况：
队伍 A B C 得分
A - 3 0 3
B 0 - 3 3
C 3 0 - 3
队伍 A B C 得分
A - 0 3 3
B 3 - 0 3
C 0 3 - 3
给出n支队伍的最终得分（即所有比赛均已结束），统计有多少种可能的分数表。
Input
第一行包含一个正整数n，队伍的个数。第二行包含n个非负整数，即每支队伍的得分。
Output
输出仅一行，即可能的分数表数目。保证至少存在一个可能的分数表。
Sample Input
样例输入1：
3
3 3 3
样例输入2：
2
0 3
样例输入3：
3
4 1 2
样例输入4：
6
5 6 7 7 8 8
Sample Output
样例输出1：
2
样例输出2：
1 样例输出3：
1
样例输出4：
121
Data Constraint
Hint
【数据规模】
数据 1 2~3 4~6 7~12 13~19 20~25
n 3 4 5 6 7 8
#include<bits/stdc++.h>using namespace std;
const int MAXN = 1e6 + 5;
#define ll long long
int n,a[10],b[10];
int ans = 0;
int score[5] = {3,1,0,0};
void dfs(int x,int y)
{
if(b[x] > a[x]) return;
if(x == n && b[x] == a[x])
{
ans++;
return;
}
if(y == n)
{
int t = a[x] - b[x];
if(t == 2) return;
b[y] += score[t];
dfs(x+1,x+2);
b[y] -= score[t];
}
else{
b[x] += 3;
dfs(x,y+1);
b[x] -= 3;
b[y] += 3;
dfs(x,y+1);
b[y] -= 3;
b[x] += 1;
b[y] += 1;
dfs(x,y+1);
b[x] -= 1;
b[y] -= 1;
}
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
}
dfs(1,2);
printf("%d",ans);
return 0;
}