A. Bark to Unlock
#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma
#define
#define
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int main()
{
// freopen("a.in","r",stdin);
// freopen(".out","w",stdout);
char s[100];
scanf("%s",s);
int n=read();
bool fl=0,fl1=0,fl2=0;
For(i,n) {
char s2[100];
scanf("%s",s2);
if (strcmp(s,s2)==0) fl=1;
if (s[1]==s2[0]) fl1=1;
if (s[0]==s2[1]) fl2=1;
}
if (fl || (fl1&&fl2)) {
puts("YES");
}else puts("NO");
return 0;
}
B. Race Against Time
石英钟坐标可能不在整点
#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma
#define
#define
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int main()
{
// freopen("B.in","r",stdin);
// freopen(".out","w",stdout);
double h=5*read()%60,m=read(),s=read();
h+=m/60/5+s/60/60/5;
m+=s/60;
int t1=read(),t2=read();
t1=t1*5%60;
t2=t2*5%60;
if(t1>t2) swap(t1,t2);
bool fl=0,fl2=0;
if (t1<h&&h<t2) fl=1;
if (t1<m&&m<t2) fl=1;
if (t1<s&&s<t2) fl=1;
if (!(t1<=h&&h<=t2)) fl2=1;
if (!(t1<=s&&s<=t2)) fl2=1;
if (!(t1<=m&&m<=t2)) fl2=1;
puts((fl&&fl2) ?"NO":"YES");
return 0;
}
C. Qualification Rounds
贪心发现最多只要取2场比赛
#include<bits/stdc++.h>
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma
#define
#define
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int c[100]={};
int main()
{
// freopen("c.in","r",stdin);
// freopen(".out","w",stdout);
int n=read(),k=read();
Rep(i,n) {
int j=0;
Rep(l,k) j=j*2+(1^read());
c[j]++;
}
int S=1<<k;S--;
if (c[S]) puts("YES");
else {
Rep(i,S) Rep(j,S) if (i!=j &&c[i]&&c[j] &&((i|j)==S)) {
puts("YES");return 0;
}
puts("NO");
}
return 0;
}
F. Yet Another Minimization Problem
莫队+四边形不等式
通过四边形不等式证明cost(i,j)满足四边形不等式
k题n很小，把模型变为，f(i)=f(j)+cost(i,j)
显然可以利用单调性 + 二分转移 。
计算的时候使用莫队，在本题中莫队保证线性。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cctype>
#include<ctime>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define MAXN (100020+10)
typedef long long ll;
int a[MAXN];
int b[MAXN]={0};
int h[MAXN]={},tcase=0;
long long Ti2=0;
int n,m;
int ll1=1,rr1=0;
ll calc(int ll2,int rr2) {
if (ll1<ll2) Fork(j,ll1,ll2-1) b[a[j]]*=(h[a[j]]==tcase),h[a[j]]=tcase,Ti2-=(long long)b[a[j]]*(b[a[j]]-1)/2,b[a[j]]--,Ti2+=(long long)b[a[j]]*(b[a[j]]-1)/2;
if (ll2<ll1) Fork(j,ll2,ll1-1) b[a[j]]*=(h[a[j]]==tcase),h[a[j]]=tcase,Ti2-=(long long)b[a[j]]*(b[a[j]]-1)/2,b[a[j]]++,Ti2+=(long long)b[a[j]]*(b[a[j]]-1)/2;
if (rr1<rr2) Fork(j,rr1+1,rr2) b[a[j]]*=(h[a[j]]==tcase),h[a[j]]=tcase,Ti2-=(long long)b[a[j]]*(b[a[j]]-1)/2,b[a[j]]++,Ti2+=(long long)b[a[j]]*(b[a[j]]-1)/2;
if (rr2<rr1) Fork(j,rr2+1,rr1) b[a[j]]*=(h[a[j]]==tcase),h[a[j]]=tcase,Ti2-=(long long)b[a[j]]*(b[a[j]]-1)/2,b[a[j]]--,Ti2+=(long long)b[a[j]]*(b[a[j]]-1)/2;
ll1=ll2,rr1=rr2;
return Ti2;
}
void reset() {
ll1=1,rr1=0;
++tcase;Ti2=0;
}
#define MAXK (30)
ll f[MAXN][MAXK];
void dfs(int k,int l,int r,int ll1,int rr1) {
int i=(l+r)/2;
f[i][k]=1e16;
int LL=max(ll1,k-1),RR=min(rr1,i-1);
int t=-1;
ForkD(j,LL,RR) {
if (f[i][k]> f[j][k-1] + calc(j+1,i)) t=j;
f[i][k] = min(f[i][k], f[j][k-1] + calc(j+1,i));
}
int m=i;
if (l<m) dfs(k,l,m-1,ll1,t);
if (m+1<=r) dfs(k,m+1,r,t,rr1);
}
int main()
{
// freopen("d.out","r",stdin);
// freopen("f.out","w",stdout);
scanf("%d%d",&n,&m);
For(i,n) scanf("%d",&a[i]);
For(i,n) For(j,m) f[i][j]=1e15;
For(i,n) f[i][1]=calc(1,i);
Fork(k,2,m) {
bool fl=0;
dfs(k,k,n,1,n);
}
cout<<f[n][m]<<endl;
return 0;
}