赛时 rank43，T1 100,T2 31,T3 0,T4 9
T2 由于学校机子的O2跑的还没有本地的O1快(太快啦！！！),挂了40pts
T4 暴力没有取模和特判，挂了5pts
与和
签到题
由于\(x\&y=a\),所以有\(x+y=s\ge2*a\)
考虑二进制下的加法，如果有一个\(sth\)满足\(a*2+sth=s\)，那么\(sth\&a\)一定为0。
将\(s-a*2\)的二进制表示出来，与\(a\)按位与，如果不为0，那么就为No，反之为Yes。
注意特判\(s-2*a<0\)的情况，此时答案一定为No。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
inline void solve(){
int T;cin>>T;
while(T--){
ll a,s;
cin>>a>>s;
ll c = s-a*2;
if(c < 0){cout<<"No\n";continue;}
bool flag = c&a;
cout<<(flag?"No\n":"Yes\n");
}
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
函数
赛时将输入random_shuffle了
然后赛后试了试，卡了卡时，学校oj可以拿97，AT上WA一个
有模拟退火+卡时过的，正解是推柿子。
如果\(f_1(f_2(x))>f_2(f_1(x))\)，那么有\(A_1A_2x+A_1B_2+B_1>A_2A_1x+A_2B_1+B_2\)
再推一下，就有\(B_2(A_1-1)>B_1(A_2-1)\)，然后还有\(\frac{B_2}{A_2-1}>\frac{B_1}{A_1-1}\)
按照\(\frac{B}{A-1}\)降序排列，写个\(O(nk)\)的背包就过了。
时间复杂度\(O(nk+n\log n)\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e5 + 10;
struct node{int a,b,id;}a[N];
int n,k;
ll f[20];
inline void solve(){
cin>>n>>k;
for(int i = 1;i <= n; ++i){
cin>>a[i].a>>a[i].b;
a[i].id = i;
}
ll res = 0;
sort(a+1,a+1+n,[](node x,node y){return 1.0*x.b/(x.a-1) > 1.0*y.b/(y.a-1);});
for(int j = 0;j <= k; ++j)f[j] = 1;
for(int i = 1;i <= n; ++i){
for(int j = k;j >= 1; --j){
f[j] = max(f[j],a[i].a*f[j-1]+a[i].b);
}
}
cout<<f[k];
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
袋鼠
预设型dp
考虑转化题意，就是一个1n的排列，满足s为第一位，t为最后一位，对于第2n-1位，两边的数同时大于或小于它的方案数。
设\(f_{i,j}\)表示已经将前i个数，分成了j段的方案数。
对于当前枚举到的数\(i\)摆放的位置进行分讨。
- 新开一段 :
因为后面加的数一定比\(i\)大，所以以后插在\(i\)两边的数一定合法，插入前有\(j-1\)段，有j个空可以放。
但如果\(i>s\)则头不能放，如果\(i>t\)则尾不能放。
所以有
\[f_{i,j}=(j-[i>s]-[i>t])\times f_{i-1,j-1} \]- 接在某一段的头或者尾
不合法
- 将两段连起来
上一步有\(j-1\)段，有\(j\)个空可以插。
所以有
\[f_{i,j}=j\times f_{i-1,j+1} \]- 对于s,t的特殊处理
只可能插在最前面或最后面，要么是自己新开了一段，要么接在某一段头部或尾部
所以有
\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j} \]目标为\(f_{n,1}\)，初始状态为\(f_{1,1}=1\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e3 + 10,mod = 1e9 + 7;
int n,s,t,f[N][N];
inline void solve(){
cin>>n>>s>>t;
f[1][1] = 1;
for(int i = 2;i <= n; ++i){
for(int j = 1;j <= i; ++j){
if(s != i && t != i)
f[i][j] = (1ll*j*f[i-1][j+1]%mod + 1ll*(j-(i>s)-(i>t))*f[i-1][j-1]%mod)%mod;
else f[i][j] = (f[i-1][j-1] + f[i-1][j])%mod;
}
}
cout<<f[n][1];
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
最短路
题目不难，放个*3000不算难吧
不会写，以后有能力做vjudge题单时再写
挂个标签 : 可持久化线段树，hash，最短路
标签：暑假,int,freopen,long,集训,FILE,using,csp,define From： https://www.cnblogs.com/hzoi-Cu/p/18367925