http://codeforces.com/contest/961
B题 可以将长度为k的连续区间转化成1 求最大和
解析 简单尺取
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <utility>
using namespace std;
const int maxn = 2e5+,maxm = 1e4+;
const int inf = 0x3f3f3f3f,mod = ;
const double epx = 1e-;
typedef long long ll;
const ll INF = 1e18;
const double pi = acos(-1.0);
int n,m,k;
int a[maxn],b[maxn];
int main()
{
cin>>n>>k;
for(int i=;i<=n;i++)
{
cin>>a[i];
}
int sum=;
for(int i=;i<=n;i++)
{
cin>>b[i];
if(b[i])
sum+=a[i];
}
int maxx=-;
int l=,r=,temp=;
while(l<=n-k+)
{
if(r-l<k)
{
if(b[r]==)
temp+=a[r];
r++;
}
else
{
//cout<<l<<" "<<r<<" "<<temp<<endl;
maxx=max(maxx,temp+sum);
if(b[l]==)
sum-=a[l];
l++;
}
}
cout<<maxx<<endl;
}
C题 棋盘分成了大小相同的四块 替换最少的方块 组成一个合格（0,1不相邻）的棋盘
j解析 对于一个合格的棋盘只有两种情况 左上角1 左上角0 四块拼成大棋盘的组合情况有24种 数组范围不大直接每种都跑一边就好了
其实直接枚举6种就好了哪两块左上角为1 C(4,2)
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <utility>
using namespace std;
const int maxn = 1e2+,maxm = 1e4+;
const int inf = 0x3f3f3f3f,mod = ;
const double epx = 1e-;
const double pi = acos(-1.0);
typedef long long ll;
const ll INF = 1e18;
int n,m,k,sum;
char a[][maxn][maxn];
char g[*maxn][*maxn];
int vis[*maxn][*maxn];
int dir[][]={{,},{-,},{,},{,-}};
int aa[],xu[][],cnt=;
void dfs(int cur,int n)
{
for(int i=;i<n;i++)
aa[i]=i+cur;
do{
for(int i=;i<n;i++)
xu[cnt][i]=aa[i];
cnt++;
}while(next_permutation(aa,aa+));
}
void DFS(int x,int y,char z)
{
vis[x][y]=;
if((x+y)%==&&g[x][y]!=z)
sum++;
else if((x+y)%==&&g[x][y]==z)
sum++;
for(int i=;i<;i++)
{
int x1=x+dir[i][];
int y1=y+dir[i][];
if(vis[x1][y1]==&&x1>=&&x1<=*n-&&y1>=&&y1<=*n-)
{
DFS(x1,y1,z);
}
}
}
int main()
{
cin>>n;
dfs(,);
int minn=inf;
for(int i=;i<=;i++)
{
for(int j=;j<n;j++)
{
cin>>a[i][j];
}
}
for(int i=;i<cnt;i++)
{
for(int j=;j<;j++)
{
if(j==)
{
for(int k=;k<n;k++)
{
for(int l=;l<n;l++)
{
g[k][l]=a[xu[i][j]][k][l];
}
}
}
else if(j==)
{
for(int k=;k<n;k++)
{
for(int l=;l<n;l++)
{
g[k][l+n]=a[xu[i][j]][k][l];
}
}
}
else if(j==)
{
for(int k=;k<n;k++)
{
for(int l=;l<n;l++)
{
g[k+n][l]=a[xu[i][j]][k][l];
}
}
}
else if(j==)
{
for(int k=;k<n;k++)
{
for(int l=;l<n;l++)
{
g[k+n][l+n]=a[xu[i][j]][k][l];
}
}
}
}
memset(vis,,sizeof(vis));
sum=;DFS(,,'');
minn=min(minn,sum);
memset(vis,,sizeof(vis));
sum=;DFS(,,'');
minn=min(minn,sum);
}
cout<<minn<<endl;
}
D题 n个点 问是否都在 某一条或某两条直线上
解析 n<3 yes n>=3 对于任意三个点a,b,c 若a,b在一条直线上L,除去在L的点，如果剩下的的点在一条直线上 有解
若a,c在一条直线上L，除去在L的点，如果剩下的的点在一条直线上 有解
若b,c在一条直线上L，除去在L的点，如果剩下的的点在一条直线上 有解
若三种情况都没有解 则无解
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <utility>
using namespace std;
const int maxn = 1e6+,inf = 0x3f3f3f3f,mod = ;
const double epx = 1e-;
const double pi = acos(-1.0);
typedef long long ll;
const ll INF = 1e18;
int n,m,k;
typedef pair<int,int> pii;
pii p[maxn];
int vis[maxn];
pii operator -(const pii &a,const pii &b)
{
return {a.first-b.first,a.second-b.second};
}
ll cross(const pii &a,const pii &b)
{
return a.first*1ll*b.second-a.second*1ll*b.first;
}
bool check()
{
int i1=-,i2=-;
for(int i=;i<n;i++)
{
if(vis[i])
continue;
if(i1==-)
i1=i;
else if(i2==-)
i2=i;
}
if(i2==-)
return true;
for(int i=;i<n;i++)
{
if(vis[i])
continue;
if(cross(p[i2]-p[i1],p[i]-p[i1])!=)
return false;
}
return true;
}
bool check2(pii a,pii b)
{
memset(vis,,sizeof(vis));
for(int i=;i<n;i++)
{
if(cross(b-a,p[i]-a)==)
vis[i]=;
}
return check();
}
int main()
{
cin>>n;
for(int i=;i<n;i++)
cin>>p[i].first>>p[i].second;
if(n<=)
cout<<"YES"<<endl;
else
{
if(check2(p[],p[])||check2(p[],p[])||check2(p[],p[]))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return ;
}