由于之前打过了这场比赛的E题，而后面两道题太难，所以就手速半个多小时A了前4题。
就当练手速吧，不过今天除了C题数组开小了以外都是1A
A Tetris
题意的抽象解释可以在Luogu里看一下（话说现在Luogu是真的好用）
非常入门的一道题，建模转化后扫一遍找出最小值即可
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
int a[N],n,m,x,ans;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc(); int flag=1;
while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=tc(); }
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
x*=flag;
}
int main()
{
register int i;
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
read(n); read(m);
for (i=1;i<=m;++i)
read(x),++a[x];
for (ans=1e9,i=1;i<=n;++i)
ans=a[i]<ans?a[i]:ans;
printf("%d",ans);
return 0;
}
B Lecture Sleep
照样可以在Luogu中查看抽象题意
B题的话比A题稍微要动一点脑子，直接暴力搞可能会T（这我没试过，但CF的数据你懂的）
因此我们开前缀和优化：
-
fact[i]表示实际a[i]的前缀和(即考虑t[i]的影响)
-
sum[i]表示理论上a[i]的前缀和(即不考虑t[i]的影响)
因此对于每一个i，即有：
ans=max(ans,fact[i-1]+fact[n]-fact[i+k-1]+sum[i+k-1]-sum[i-1]);
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+5;
int a[N],sum[N],fact[N],n,k,x,ans;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc(); int flag=1;
while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=tc(); }
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
x*=flag;
}
inline int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
register int i;
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
read(n); read(k);
for (i=1;i<=n;++i)
read(a[i]),sum[i]=sum[i-1]+a[i];
for (i=1;i<=n;++i)
read(x),fact[i]=fact[i-1]+a[i]*x;
for (ans=-1,i=1;i<=n;++i)
ans=max(ans,fact[i-1]+fact[n]-fact[i+k-1]+sum[i+k-1]-sum[i-1]);
printf("%d",ans);
return 0;
}
C Chessboard
题意：一块国际象棋棋盘（满足黑白相间）碎成了均匀的2*2小块（黑白块个数不一定合法）。现在你可以把它们任意地拼起来，问一种方案使得它与正确的棋盘黑白块的个数相差最少（0,1表示黑白块）
这就是大力搜索题，思路很简单：暴力出所有组合方案，然后for一遍判断即可
注意棋盘左上角的颜色可以是黑白两种
CODE
#include<iostream>
#include<cstring>
using namespace std;
const int N=105;
bool a[10][N][N],map[N<<1][N<<1],vis[10];
int n,ans=1e9,c[10];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void copy(int opt,int num)
{
register int i,j;
if (opt==1)
{
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
map[i][j]=a[num][i][j];
}
if (opt==2)
{
for (i=1;i<=n;++i)
for (j=n+1;j<=n<<1;++j)
map[i][j]=a[num][i][j-n];
}
if (opt==3)
{
for (i=n+1;i<=n<<1;++i)
for (j=1;j<=n;++j)
map[i][j]=a[num][i-n][j];
}
if (opt==4)
{
for (i=n+1;i<=n<<1;++i)
for (j=n+1;j<=n<<1;++j)
map[i][j]=a[num][i-n][j-n];
}
}
inline bool kinds(int opt,int x,int y)
{
return ((x+y)&1)^opt;
}
inline void work(void)
{
register int i,j;
for (i=1;i<=4;++i)
copy(i,c[i]);
int tot=0;
for (i=1;i<=n<<1;++i)
for (j=1;j<=n<<1;++j)
if (map[i][j]^kinds(0,i,j)) ++tot;
ans=min(ans,tot);
for (i=1;i<=n<<1;++i)
for (j=1;j<=n<<1;++j)
if (map[i][j]^kinds(1,i,j)) ++tot;
ans=min(ans,tot);
}
inline void DFS(int now)
{
if (now>4) { work(); return; }
for (register int i=1;i<=4;++i)
if (!vis[i])
{
vis[i]=1; c[i]=now;
DFS(now+1); vis[i]=0;
}
}
int main()
{
register int i,j,k;
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
std::ios::sync_with_stdio(false);
cin>>n;
for (k=1;k<=4;++k)
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
{
char ch;
cin>>ch; a[k][i][j]=ch-'0';
}
DFS(1);
cout<<ans;
return 0;
}
D Pair Of Lines
这是一道不错的平面几何的题目
题意是在一个平面直角坐标系中有n个整点，求是否存在两条直线使得这两条直线能经过所有的点
很显然，从中任意挑出2个点，如果有解那么这两点确定的直线一定是答案中的一条直线
所以我们可以从n个点中随机挑出2个点，删去在它们确定的直线上的点，然后判断剩下的点是否在同一条直线上
但是很显然不需要从n个点当中选取，可以简单的证明（归纳一下即可）只需要找出3个点然后在当中选两个然后按上面的方法做即可
关于两点是否在直线上除了可以用y=kx+b来求还可以用一下的斜率的方法：
(x2-x1)/(y2-y1)=(xi-x1)/(yi-y1)
其中i和点1,2都是直线上的点
为了避免精度误差，我们交叉相乘一下：
(x2-x1)*(yi-y1)=(y2-y1)*(xi-x1)
然后就很简单了
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+5;
struct data
{
int x,y;
}a[N];
int n;
bool vis[N];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc(); int flag=1;
while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=tc(); }
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
x*=flag;
}
inline void del(int p,int q)
{
memset(vis,0,sizeof(vis));
vis[p]=vis[q]=1;
int x1=a[p].x,y1=a[p].y,x2=a[q].x,y2=a[q].y,X=x2-x1,Y=y2-y1;
for (register int i=1;i<=n;++i)
if ((long long)X*(a[i].y-y1)==(long long)Y*(a[i].x-x1)) vis[i]=1;
}
inline bool check(void)
{
register int i;
int s1=0,s2=0;
for (i=1;i<=n;++i)
if (!vis[i]) { s1=i; break; }
vis[s1]=1;
for (i=1;i<=n;++i)
if (!vis[i]) { s2=i; break; }
if (!s1||!s2) return 1;
vis[s2]=1;
int x1=a[s1].x,y1=a[s1].y,x2=a[s2].x,y2=a[s2].y,X=x2-x1,Y=y2-y1;
for (i=1;i<=n;++i)
if (!vis[i]) if ((long long)X*(a[i].y-y1)!=(long long)Y*(a[i].x-x1)) return 0;
return 1;
}
int main()
{
register int i;
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
read(n);
if (n<=4) { puts("YES"); return 0; }
for (i=1;i<=n;++i)
read(a[i].x),read(a[i].y);
del(1,2); if (check()) { puts("YES"); return 0; }
del(1,3); if (check()) { puts("YES"); return 0; }
del(2,3); if (check()) { puts("YES"); return 0; }
puts("NO");
return 0;
}