2024-1-10 day1
1915G - Bicycles
inf搞大一点inf搞大一点inf搞大一点inf搞大一点inf搞大一点
其实就是多了一个条件的最短路。
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int inf = 5e18;
const int MAXN = 1010;
struct qnode{
int v;
int c;
int by;
qnode(int _v,int _c=0,int _by=0):v(_v),c(_c),by(_by){}
bool operator < (const qnode &r) const{
return c>r.c;
}
};
struct edge{
int v,w;
edge(int _v=0,int _w=0):v(_v),w(_w){};
};
vector<edge> E[MAXN];
bool vis[MAXN][MAXN];
int dist[MAXN][MAXN];
int cost[MAXN];
void dis(int n){
for(int i=0;i<=n;i++)
for(int j=0;j<=1000;j++)
{
dist[i][j] = inf;
vis[i][j] = false;
}
priority_queue<qnode> que;
while(que.size()) que.pop();
dist[1][cost[1]]=0;
que.push({1,0,cost[1]});
qnode tmp(0,0,0);
while(que.size()){
tmp=que.top();
que.pop();
int u=tmp.v;
int by=tmp.by;
if(vis[u][by]) continue;
vis[u][by]=true;
for(int i=0;i<E[u].size();i++){
int v=E[u][i].v;
int pp = min(by,cost[v]);
int len=E[u][i].w*by;
if(!vis[v][by]&&dist[v][pp]>dist[u][by]+len){
dist[v][pp]=dist[u][by]+len;
que.push(qnode(v,dist[v][pp],pp));
}
}
}
}
void addedge(int u,int v,int w){
E[u].push_back(edge(v,w));
}
void solve(){
int n,m;
cin >> n >> m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin >> u >> v >> w;
addedge(u,v,w);
addedge(v,u,w);
}
for(int i=1;i<=n;i++) cin>>cost[i];
dis(n);
long long ans = inf;
for(int i=1;i<=1000;i++) ans = min(ans , dist[n][i]);
cout << ans <<endl;
for(int i=1;i<=n;i++) E[i].clear();
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
K - Kim's Quest
痛苦啊
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;
const int mod = 998244353;
int n;
int a[N];
int dp[N][4];
//0 偶偶
//1 奇偶
//2 偶奇
//3 奇奇
int cnt[2];
int x[4];
void solve(){
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++)
{
if(a[i]&1)
{
dp[i][0] = dp[i-1][0];
dp[i][1] = dp[i-1][1];
dp[i][2] = (dp[i-1][2] + dp[i-1][1] + x[1])%mod;
dp[i][3] = (dp[i-1][3] + dp[i-1][2] + x[2])%mod;
x[2] += cnt[0];
x[3] += cnt[1];
cnt[1]++;
}
else
{
dp[i][0] = (dp[i-1][0] + dp[i-1][0] + x[0])%mod;
dp[i][1] = (dp[i-1][1] + dp[i-1][3] + x[3])%mod;
dp[i][2] = dp[i-1][2];
dp[i][3] = dp[i-1][3];
x[0] += cnt[0];
x[1] += cnt[1];
cnt[0]++;
}
//cout<<cnt[0]<<" "<<cnt[1]<<endl;
//cout << (dp[i][0]+dp[i][1]+dp[i][2]+dp[i][3])%mod <<endl;
}
cout << (dp[n][1]+dp[n][2]+dp[n][3]+dp[n][0])%mod <<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
M - Triangle Construction
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N];
void solve(){
cin >> n;
long long sum = 0;
for(int i=1;i<=n;i++)
{
cin >> a[i];
sum += a[i];
}
sort(a+1,a+1+n);
if(a[n]>=2*(sum-a[n])) cout<<sum-a[n]<<endl;
else cout<<sum/3<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}