10.11

闲话

做题纪要

luogu P3345 [ZJOI2015] 幻想乡战略游戏

luogu P5311 [Ynoi2011] 成都七中

[ABC373F] Knapsack with Diminishing Values

• 暴力

  • 分组背包写个常数小点的加 \(C++20\) 加手动开 \(O3\) 就过了（赛时直接把火车头粘上了），算下来 \(AT\) 神机能跑 \(1e10\) 。

    点击查看代码

    #include<bits/stdc++.h>
    #pragma GCC optimize(3)
    #pragma GCC target("avx")
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("inline")
    #pragma GCC optimize("-fgcse")
    #pragma GCC optimize("-fgcse-lm")
    #pragma GCC optimize("-fipa-sra")
    #pragma GCC optimize("-ftree-pre")
    #pragma GCC optimize("-ftree-vrp")
    #pragma GCC optimize("-fpeephole2")
    #pragma GCC optimize("-ffast-math")
    #pragma GCC optimize("-fsched-spec")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("-falign-jumps")
    #pragma GCC optimize("-falign-loops")
    #pragma GCC optimize("-falign-labels")
    #pragma GCC optimize("-fdevirtualize")
    #pragma GCC optimize("-fcaller-saves")
    #pragma GCC optimize("-fcrossjumping")
    #pragma GCC optimize("-fthread-jumps")
    #pragma GCC optimize("-funroll-loops")
    #pragma GCC optimize("-fwhole-program")
    #pragma GCC optimize("-freorder-blocks")
    #pragma GCC optimize("-fschedule-insns")
    #pragma GCC optimize("inline-functions")
    #pragma GCC optimize("-ftree-tail-merge")
    #pragma GCC optimize("-fschedule-insns2")
    #pragma GCC optimize("-fstrict-aliasing")
    #pragma GCC optimize("-fstrict-overflow")
    #pragma GCC optimize("-falign-functions")
    #pragma GCC optimize("-fcse-skip-blocks")
    #pragma GCC optimize("-fcse-follow-jumps")
    #pragma GCC optimize("-fsched-interblock")
    #pragma GCC optimize("-fpartial-inlining")
    #pragma GCC optimize("no-stack-protector")
    #pragma GCC optimize("-freorder-functions")
    #pragma GCC optimize("-findirect-inlining")
    #pragma GCC optimize("-fhoist-adjacent-loads")
    #pragma GCC optimize("-frerun-cse-after-loop")
    #pragma GCC optimize("inline-small-functions")
    #pragma GCC optimize("-finline-small-functions")
    #pragma GCC optimize("-ftree-switch-conversion")
    #pragma GCC optimize("-foptimize-sibling-calls")
    #pragma GCC optimize("-fexpensive-optimizations")
    #pragma GCC optimize("-funsafe-loop-optimizations")
    #pragma GCC optimize("inline-functions-called-once")
    #pragma GCC optimize("-fdelete-null-pointer-checks")
    using namespace std;
    #define ll long long 
    #define ull unsigned long long
    #define sort stable_sort 
    #define endl '\n'
    ll w[3010],v[3010],f[2][3010];
    int main()
    {
    	ll n,m,ans=0,i,j,k;
    	cin>>n>>m;
    	for(i=1;i<=n;i++)
    	{
    		cin>>w[i]>>v[i];
    	}
    	for(i=1;i<=n;i++)
    	{
    		for(j=1;j<=m;j++)
    		{
    			f[i&1][j]=f[(i-1)&1][j];
    		}
    		for(k=1;k*w[i]<=m;k++)
    		{
    			for(j=k*w[i];j<=m;j++)
    			{
    				f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-k*w[i]]+k*v[i]-k*k);
    			}
    		}
    	}
    	for(i=1;i<=m;i++)
    	{
    		ans=max(ans,f[n&1][i]);
    	}
    	cout<<ans<<endl;
    	return 0;
    }
    

[ABC366G] XOR Neighbors

CF341D Iahub and Xors