2022/2/7
2022/2/7
P1251 餐巾计划问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
建模方法参考： 题解 P1251 [餐巾计划问题] - Mark_ZZY 的博客 - 洛谷博客 (luogu.com.cn)
拆点太妙了
参考代码
#include
#define ll long long
#define pii pair
#define si size()
#define fi first
#define se second
#define pb push_back
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=2e5+7;
ll n,T,k,a[qs],b[qs];
ll s,t,p,head[qs],nxt[qs],val[qs],dis[qs],to[qs];
void add(int fx,int tx,int dx,int cx){
to[p]=tx;
dis[p]=dx;
nxt[p]=head[fx];
val[p]=cx;
head[fx]=p++;
}
void ins(int u,int v,int w,int c){
// cout<<"u="< q; q.push(s);
while(q.si){
int u=q.front(); q.pop();
inq[u]=0;
for(int i=head[u];i!=-1;i=nxt[i]){
if(dis[i]){//spfa是以费用val求最短路的，但流量不能忽略
int v=to[i];
// cout<<"v="< 方格填色 (nowcoder.com)
矩阵快速幂优化状压dp
把行列颠倒，先考虑状压dp,\(f[i][j]\)表示第i行状态为j的方案数，状态转移方程就是$f[i][j]+=f[i-1][j1] (j1|j==0 && j!=j1) $
由于行数 \(n<=1e18\),暴力不可取。
由于状态转移成线性关系，考虑矩阵快速幂。
关系矩阵可根据 $ (j1|j==0 && j!=j1)$构造
关系矩阵自乘n-1次中所有数的总和即是答案
(可以把矩阵快速幂扔到校赛去（逃
参考代码
#include
#define ll long long
#define pii pair
#define si size()
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=2e5+7;
int n,m;
struct Matrix {//矩阵初始化，乘法重载
int a[40][40];//2^5只有32，开40*40足够
Matrix()
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = 0;
}
}
}
Matrix operator * (const Matrix& Ma_) const
{
Matrix res;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
res.a[i][j] = (res.a[i][j] + a[i][k] * Ma_.a[k][j] % mod) % mod;
}
}
}
return res;
}
};
Matrix quickpow(Matrix res,Matrix sta, ll b)//快速幂板子
{
while (b > 0)
{
if (b & 1) res = res * sta;
sta = sta * sta;
b >>= 1;
}
return res;
}
Matrix f,p;
void build_M(){
for(int i=0;i Problem - B - Codeforces (Unofficial mirror site, accelerated for Chinese users)
注意到 + 或 xor 一个数对整体来说改变的奇偶性是一样的
那就所有的数加起来再加x，跟y的奇偶性作对比即可
#include
#define ll long long
#define pii pair
#define si size()
#define fi first
#define se second
#define pb push_back
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=2e5+7;
ll n,x,y,T,a[qs],b[qs];
int main(){
T=read();
while(T--){
n=read(),x=read(),y=read();
ll fx,sum=0;
for(int i=1;i<=n;++i){
fx=read();
sum+=fx;
}
x+=sum;
if(x&1){
if(y&1) cout<<"Alice\n";
else cout<<"Bob\n";
}
else{
if(!(y&1)) cout<<"Alice\n";
else cout<<"Bob\n";
}
}
return 0;
}
Problem - D - Codeforces (Unofficial mirror site, accelerated for Chinese users)
先随便指定两个数不变，n-2次询问其他数，得到一个最大值。
根据这个最大值的下标，再n-2次去找最大值，找到的下标即是答案。
（有些特殊情况需讨论
#include
#define ll long long
#define pii pair
#define si size()
#define fi first
#define se second
#define pb push_back
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const int qs=2e5+7;
map mp;
ll n,T,k;
int main(){
cin>>T;
while(T--){
cin>>n;
int m=-1,id,x;
mp.clear();
for(int i=3;i<=n;++i){
cout<<"? 1 "<<"2 "<>x;
mp[x]++;
if(x>m){
m=x;
id=i;
}
}
int fg=0;
if(mp.si==1){
fg=1;
// cout<<"!1 2\n";
// fflush(stdout);
// continue;
}
int m1=-1;mp.clear();
int f;
for(int i=2;i<=n;++i){
if(i==id) continue;
cout<<"? 1 "<>x;
mp[x]++;
if(x>m1){
m1=x;
f=i;
}
}
if(fg&&m==m1){
cout<<"! 1 2\n";
fflush(stdout);
continue;
}
if(mp.si==1){
cout<<"! 1 "< Problem - E - Codeforces (Unofficial mirror site, accelerated for Chinese users)
欧拉回路
看了大佬博客了解了思想，明天码一下。
参考博客： Fair Share （构造+欧拉回路）
每日分享
【派大星】loser－当一个粉色的失败者有什么意思_哔哩哔哩_bilibili
当梦醒时分我该启程