菜鸡第一次打icpc
记录一下历程
习惯#define int long long
以下皆是按照我认为的难易顺序排序
K.
看题意大概就是说求从L加到R
1 ios::sync_with_stdio(false);
2 cin.tie(nullptr);
3 cout.tie(nullptr);
4 int a,b;
5 cin>>a>>b;
6
7 if(a < b) swap(a,b);
8 int res =a-b+1;
9 cout<<(a+b)*res/2;
B.
贪心，同一列1多就构造1，否则就构造0
1 const int N = 1e3 + 10;
2 char s[N][N];
3 char res[N];
4
5 void solve() {
6 ios::sync_with_stdio(false);
7 cin.tie(nullptr);
8 cout.tie(nullptr);
9
10 int n, m;
11 cin >> n >> m;
12 for (int i = 1; i <= n; ++i) {
13 cin >> (s[i] + 1);
14 }
15 for (int j = 1; j <= m; ++j) {
16 int a = 0, b = 0;
17 for (int i = 1; i <= n; ++i) {
18 if (s[i][j] == '0') b++;
19 else a++;
20 }
21 if (a > b) res[j] = '1';
22 else res[j] = '0';
23 }
24 cout << (res + 1);
25 }
G.
很裸的一个01背包问题，只不过多了一个背包，变二维了
（数据范围很坑，比赛的时候就因为数据范围的时候一直爆内存错误，下来了把空间开大了就过了）
1 const int N = 510;
2 int n, v1, v2;
3 int v[N], w1[N], w2[N];
4 int dp[N][N];
5 void solve() {
6 cin >> n >> v1 >> v2;
7 for (int i = 1; i <= n; ++i) {
8 cin >> v[i] >> w1[i] >> w2[i];
9 }
10 for(int i =1;i <= n;++i)
11 for(int j = 0;j <= v1;++j)
12 for(int k = 0;k <= v2;++k){
13 if(j >= v[i]) dp[j][k] = max(dp[j][k],dp[j-v[i]][k]+w1[i]);
14 if(k >= v[i]) dp[j][k] = max(dp[j][k],dp[j][k-v[i]]+w2[i]);
15 }
16 cout<<dp[v1][v2]<<"\n";
17 }
A.
可以说是dfs吧，从根节点搜到底，如果碰到节点没有后继，说明食物链+1
从底层的节点向上更新数据，最后输出根节点的最大价值
（比赛的时候想复杂了，用层序遍历从底层节点向上更新，虽然总的想法差不多，但是在处理边权的时候需要不断重复的搜边造成时间爆炸
而且也没什么好的办法优化这种搜边的问题，最后卡在6s了）
const int N = 2e6+10,mod = 32416190071;
int n;
int f[N];
int pre[N];
bool st[N];
int ans = 0;
int e[N],ne[N],h[N],idx,w[N];
void add(int a,int b,int v){
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx++;
} void dfs(int root){
if(h[root] == -1){
ans ++;
}
f[root] = pre[root] % mod;
for(int i = h[root];~i;i = ne[i]){
int j = e[i],c = w[i];
dfs(j);
f[root] = (f[root]+f[j]*c)%mod;
} } signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n;
memset(h,-1,sizeof (h));
for(int i = 1;i < n;++i){
int a,b,v;
cin>>a>>b>>v;
add(a,b,v);
st[b] = true;
}
int root = 0;
for(int i = 1;i <= n;++i) if(!st[i]){
root = i;
break;
}
for(int i =1;i <= n;++i){
cin>>pre[i];
}
dfs(root);
cout<<ans<<"\n"<<f[root]<<"\n";
return 0;
}
菜鸡就只能做到这了，大概总结一下
比较有问题的地方在数据范围和c++输入输出没加速（血泪教训）
别的题感觉数论好多，难受不会
