A.生死逆转
简单的模拟题
我们只需要按照题目意思模拟即可，明显的我要答案最大一定是变化最小的，要答案最小一定是变化最大的,排序一下即可
void solve(){
cin>>n;
LL ans = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
ans += a[i];
}
sort(a+1,a+1+n);
LL z = ans,f=ans;
z-=2*a[1];
z-=2*a[2];
f-=2*a[n];
f-=2*a[n-1];
cout << z << endl << f << endl;
return ;
}
B.逃跑路线
topsort
我们都题目可以发现是有进有出的多源多终点的无权图，要的是方案数，我们可以想到使用topsort,只有满足当前这个点的入度点都被使用过了才可以使用他去更新别人,用in数组来维护入度，out数组维护这个点的出度
vector<int> g[N];
int in[N];
int out[N];
int d[N];
void solve(){
cin>>n>>m;
while(m--){
int a,b; cin>>a>>b;
in[a]++;
g[b].push_back(a);
out[b]++;
}
queue<int> q;
for(int i=1;i<=n;i++) if(!in[i]) {d[i]=1,q.push(i);}
while(!q.empty()){
int u = q.front(); q.pop();
for(auto&v:g[u]){
d[v]+=d[u];
d[v]%=mod;
if(--in[v]==0) q.push(v);
}
}
LL ans = 0;
for(int i=1;i<=n;i++)
if(!out[i]){
ans+=d[i];
ans%=mod;
}
cout << ans << endl;
return ;
}
C.借来用用
二分+排序
题目告诉我们要按照谁先借借谁，但是没说按照时间给出所以我们要进行排序操作，接着分析性质，每一个人的影响是[a,b]使用了d，维护区间操作我们可以想到差分，前缀和，我们要找的是第一个不满足的，判断是否具有二分性质，如果说当前不满足了，后面肯定不满足，当前满足前面一定满足，所以可以使用二分，我们就用差分+前缀和维护前面使用的，来比较原来有没有超过即可
vector<PII> g[N];
LL w[N];
struct code{
int d,a,b,id;
bool operator<(const code&t)const{
return a<t.a;
}
}e[N];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=m;i++){
int d,a,b; cin>>d>>a>>b;
e[i]={d,a,b,i};
}
sort(e+1,e+1+m);
auto check = [&](int r){
vector<LL> c(n+5);
for(int i=1;i<=r;i++){
auto [d,a,b,id]=e[i];
c[a]+=d,c[b+1]-=d;
}
for(int i=1;i<=n;i++) c[i]+=c[i-1];
for(int i=1;i<=r;i++) if(c[i]>w[i]) return false;
return true;
};
int l=1,r=n;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
if(l==n and check(l)) cout << 0 << endl;
else cout << -1 << endl << e[l].id << endl;
return ;
}
D.Balatro
中等模拟
首先理清楚题目意思，对于模拟题，重复的同时便于使用函数的我们一般考虑使用函数，代码不用怕长主要是要清晰,我们依照题目意思 把当前牌按照下面的方式来划分不同类型,同时只有被划分计算的才有底牌的分(三条是看三条的贡献其他俩不看) 然后我们一步一步按照题目意思模拟，注意到“A 1 2 3 4”也是顺子，我们可以考虑把字母和数字分离开(判断同花和顺子便简洁),J,Q,K,Q依次看成11，12，13，14这样方便判断顺子，我们可以额外写两个函数辅助判断,同时注意到当一个牌计入贡献是是固定的可以写一个get函数得到贡献，到看一样的牌了，用cnt数组记录即可，然后从4，3&2，2&2,2,高牌的顺序写下去即可，重点是要注意自己逻辑的清晰
string s[6];
struct code{
char x;
int v;
bool operator<(const code&t)const{
return v<t.v;
}
}e[N];
int get(int x){ // 判断贡献
if(2<=x and x<=10) return x;
if(x==14) return 11;
return 10;
}
bool shun(){ // 判断顺子
int last = e[1].v;
for(int i=2;i<=n;i++){
auto [x,v]=e[i];
if(last+1==v) last = v;
else {
if(i==n and last==5 and v==14) continue;
return false;
}
}
return true;
}
bool hua(){ // 判断同花
char last = e[1].x;
bool ok = true;
for(int i=2;i<=n;i++){
auto [x,v]=e[i];
if(last!=x) ok = false;
}
return ok;
}
void solve(){
n=5;
for(int i=1;i<=n;i++) cin>>s[i];
map<char,int> mp{{'J',11},{'Q',12},{'K',13},{'A',14}};
for(int i=1;i<=n;i++){
auto v = s[i];
if(mp.count(v[1])){
e[i]={v[0],mp[v[1]]};
continue;
}
int t = 0;
for(int i=1;i<v[i];i++) t=t*10+(v[i]-'0');
e[i]={v[0],t};
}
sort(e+1,e+1+n);
LL ans = 0;
if(shun()){ // 顺子
// 检查是不是同
LL ans = 0;
for(int i=1;i<=n;i++){
auto [x,v]=e[i];
ans += get(v);
}
// 1.同花顺子
if(hua()){
ans += 100;
ans *= 8;
cout << ans << endl;
}
else{// 2.普通顺子
ans+=30;
ans*=4;
cout << ans << endl;
}
return ;
}
if(hua()){
LL ans = 0;
for(int i=1;i<=n;i++){
auto [x,v]=e[i];
ans += get(v);
}
ans += 35;
ans *= 4 ;
cout << ans << endl;
return ;
}
vector<int> cnt(15);
for(int i=1;i<=n;i++){
auto [x,v]=e[i];
cnt[v]++;
}
int four = 0;
int three = 0;
int two = 0;
for(int i=1;i<=15;i++){
if(cnt[i]==4) four = i;
if(cnt[i]==3) three = i;
if(cnt[i]==2) two ++ ;
}
// 是不是有四个一样的
if(four){
for(int i=1;i<=n;i++){
auto [x,v]=e[i];
if(cnt[v]!=4) continue;
ans += get(v);
}
ans+=60;
ans*=7;
cout << ans << endl;
return ;
}
if(three){
if(two){
for(int i=1;i<=n;i++){
auto [x,v]=e[i];
ans += get(v);
}
ans += 40;
ans *=4;
cout << ans << endl;
}
else{
for(int i=1;i<=n;i++){
auto [x,v]=e[i];
if(cnt[v]!=3) continue;
ans += get(v);
}
ans += 30;
ans *= 3;
cout << ans << endl;
}
return ;
}
if(two){
for(int i=1;i<=n;i++){
auto [x,v]=e[i];
if(cnt[v]!=2) continue;
ans += get(v);
}
if(two==2){
ans += 20;
ans *=2;
}
else{
ans += 10;
ans *= 2;
}
cout << ans << endl;
return ;
}
// 高牌
int t = e[n].v;
ans += get(t);
ans += 5;
cout << ans << endl;
return ;
}
E.旅行
图论
赛时没有认真分析惨遭被T飞了20多发QWQ,最后没过
那么我们现在来分析一手，首先这个减去的费用是变化的，我们可以发现而且是越来越大,注意到数据范围是1000级别，应该是的解题时间复杂度,同时注意到m(贡献)是1000级别的,如果说t越来越大后面肯定是不划算的，比如第i次是c*
,第i+1次就是c*
+c*(2*i+1)，要多扣除2i+1的次数,也就是说走了1000之后一定是不划算的贡献为减法了,所以我们可以发现每个点也就是1000个状态，表示走到当前点是第几次的最优解,我们可以只用跑一个简单的dp即可
dp[b][i]=max(dp[b][i],dp[a][i-1]+w[b]-c(2*i-1) 时间就是
(N=1000)
其实就是bellman-ford算法
vector<PII> g;
LL f[N][N],w[N];
void solve(){
cin>>n>>m>>c;
for(int i=1;i<=n;i++) cin>>w[i];
while(m--){
int a,b; cin>>a>>b;
g.push_back({a,b});
}
for(int i=1;i<=n;i++)
for(int j=0;j<N;j++)
f[i][j]=-4e18;
f[1][0]=0;
LL ans = 0;
for(int i=1;i<N;i++){
for(auto&[a,b]:g){
f[b][i]=max(f[a][i-1]+w[b]-c*(2*i-1),f[b][i]);
}
ans = max(ans,f[1][i]);
}
cout << ans << endl;
return ;
}
接下来简单分析一下错误代码 我们依照上面的方式跑一个dijkstra,如果使用st[a][i]去标记当前状态被使用过只有30分,因为dijkstra无法求解最长路不=具有最短路的性质的
LL d[N][N];
int st[N][N];
LL w[N];
void solve(){
cin>>n>>m>>c;
for(int i=1;i<=n;i++)
cin>>w[i];
while(m--){
int a,b; cin>>a>>b;
g[a].push_back(b);
}
auto dijkstra = [&](){
queue<tuple<LL,LL,LL>> q;
q.emplace(0,0,1);
while(!q.empty()){
auto [cost,dt,u]=q.front(); q.pop();
for(auto&v:g[u]){
LL now = cost + w[v] - (2*dt+1)*c;
if(d[v][dt+1]<now){
d[v][dt+1]=now;
q.emplace(now,dt+1,v);
}
}
}
return 0;
}();
LL ans = 0;
for(int i=0;i<N;i++) ans = max(ans,d[1][i]);
cout << ans << endl;
return ;
}
如果我们把st[u][dt]去除呢，这就会导致不断的更新，每个点多次被更新时间复杂度退化所以最后会超时，由此可见认真分析的时间复杂度的重要性！
京公网安备 11010502036488号