2022icpc新疆省赛
2024-09-05 18:16:16
菜鸡第一次打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++输入输出没加速(血泪教训)
别的题感觉数论好多,难受不会
最新文章
- Android 数据传递(二)Activity与fragment之间的通信
- mongo日志切割脚本
- [Android Pro] AIDL进程间传递自定义类型参数
- VC++ AfxBeginThread 与 CreateThread 的区别
- spoj LCMSUM sigma(lcm(i,n));
- Win32/MFC的基本概念
- C#编写Windows服务程序图文教程(转载)
- cronjob不跑得原因
- POJ 3177 Redundant Paths POJ 3352 Road Construction(双连接)
- Android LayoutInflater解析
- flash/flex 编译错误汇总
- 阿里图标库iconfont入门使用
- XSS(跨域脚本攻击)应对之道
- 移动App测试中的最佳做法
- 团队作业3——alpha阶段冲刺
- K XOR Clique
- 深入理解java虚拟机---JDK8-废弃永久代(PermGen)迎来元空间(Metaspace)(十二)
- Flex学习笔记-皮肤
- Python3实战系列之一(获取印度售后数据项目)
- Linux Shell脚本入门--wc命令