原谅自己迟到的有点厉害
感觉打的还行,一个一血(K)
主代码手写的真累...
B题
诡异的思路..
C(n,m) = C(n-1,m-1) + C(n-1,m)
我们递归2层,我们可以发现
C(n,0) + C(n,1) + ... + C(n,m)
= 4 * (C(n-2,0) + C(n-2,1) + ... + C(n-2,m-2)) + 3 * C(n-2,m-1) + C(n-2,m)
我们发现递归x层,前面的部分都是2的x次方,后面x项不定
开始打表,每200个打一次表,记录答案
然后如果m<=200就暴力,m>200就递归下去,到一个200的倍数层
例如500就递归到400,也就是递归100层
我们最后100前面的权值可以手算
当然它的值实际上就是C(100,0) + C(100,1) + ... 这么计算的
所以预处理一下也就可以了
D题
题目出错了(2次)不多吐槽...
巨慢的通过时间,巨大罚时
a=1,直接把b排序 选前若干个
然后看是否比它们乘起来要大就行
E题
烦死人的讨论...
noname提供了一发做法..
具体的来说把这个矩形翻成一个大三角形(大概长这样)
1
2 3
4 5 6
....
然后就是在这个大三角形里面每次找个斜的平行四边形去更新答案
平行四边形 = 上三角 + 中间的平行四边形 + 下三角
然后分别求...
G题
lyc写的
J题
数独.....
看上去4^16*16复杂度,但是由于它是数独实际上跑得飞快...
15ms过
K题
如果前面是一个数字0,那么后面一定要一个符号
如果前面是个符号,后面需要一个数字0或者一个1~9带头的数字
如果前面是0,问号当加号用
不然问号当1用即可
L题
直接从1到n是最优的
理由不知道....
=================
B
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int fact[100005];
int anti_fact[100005];
const int modo=1000000007;
int power(int x,int y)
{
if (y==0) return 1;
int t=power(x,y/2);
t=(long long)t*t%modo;
if (y%2==1)
{
t=(long long)t*x%modo;
}
return t;
}
int val[505][100005];
int temp[205][205];
int c(int n,int m)
{
if (m>n) return 0;
return fact[n]*(long long)anti_fact[m]%modo*anti_fact[n-m]%modo;
}
int main()
{
int i;
fact[0]=1;
for (i=1;i<=100000;i++)
{
fact[i]=(long long)fact[i-1]*i%modo;
}
anti_fact[0]=1;
for (i=1;i<=100000;i++)
{
anti_fact[i]=power(fact[i],modo-2);
}
for (i=0;i<=100000;i+=200)
{
int j;
for (j=0;j<=100000;j++)
{
val[i/200][j]=c(i,j);
if (j!=0)
{
val[i/200][j]+=val[i/200][j-1];
if (val[i/200][j]>=modo) val[i/200][j]-=modo;
}
}
}
for (i=0;i<=200;i++)
{
int j;
for (j=0;j<=200;j++)
{
temp[i][j]=c(i,j);
if (j!=0)
{
temp[i][j]+=temp[i][j-1];
if (temp[i][j]>=modo) temp[i][j]-=modo;
}
}
}
int t;
scanf("%d",&t);
int zu;
for (zu=0;zu<t;zu++)
{
int n,m;
scanf("%d%d",&n,&m);
if (m<=200)
{
int sum=0;
for (i=0;i<=m;i++)
{
sum+=c(n,i);
if (sum>=modo) sum-=modo;
}
printf("%d
",sum);
}
else
{
int k=n%200;
int sum=(long long)val[n/200][m-k]*power(2,k)%modo;
int i;
n-=k;
int p=1;
for (i=0;i<k;i++)
{
sum=(sum+(long long)c(n,m)*temp[k][i])%modo;
m--;
p*=2;
if (p>=modo) p-=modo;
}
printf("%d
",sum);
}
}
return 0;
}
D
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int b[105];
int main()
{
int t;
scanf("%d",&t);
int zu;
for (zu=0;zu<t;zu++)
{
int n,m;
scanf("%d%d",&n,&m);
int i;
for (i=0;i<n;i++)
{
scanf("%d",&b[i]);
scanf("%d",&b[i]);
}
sort(b,b+n);
for (i=0;i<n;i++)
{
m/=(b[i]+1);
if (m==0) break;
}
printf("%d
",i);
}
return 0;
}
E
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int l;
int a[1005];
long long ans=0;
int L2;
int L;
long long getpos(long long x, long long y)
{
return x * (x + 1) / 2 + y;
}
long long sum(long long x, long long y, long long h, long long w, int tag)
{
long long ret = 0, l, r, nowsum;
if (!tag)
{
h = h - x + 1;
w = w - y + 1;
for (int i = 0; i < L2; i++)
{
l = getpos(x + i, y);
r = getpos(x + i, y + w - 1);
nowsum = 0;
for (int j = 0; j < L; j++) nowsum += a[j] * ((r - j + L) / L - (l - 1 - j + L) / L);
ret += nowsum * ((h - i - 1 + L2) / L2);
}
}
else
{
h = h - x + 1;
w = w - y - h + 2;
for (int i = 0; i < L2; i++)
{
l = getpos(x + i, y + i);
r = getpos(x + i, y + i + w - 1);
nowsum = 0;
for (int j = 0; j < L; j++) nowsum += a[j] * ((r - j + L) / L - (l - 1 - j + L) / L);
ret += nowsum * ((h - i - 1 + L2) / L2);
}
}
return ret;
}
long long get_res(int x,int y)
{
return a[((long long)x*(x+1)/2+y)%l];
}
long long calc_line(int x,int y1,int y2)
{
if (y1>y2)
{
printf("gg
");
}
long long l = getpos(x , y1);
long long r = getpos(x , y2);
long long nowsum = 0;
for (int j = 0; j < L; j++) nowsum += a[j] * ((r - j + L) / L - (l - 1 - j + L) / L);
return nowsum;
}
long long calc_small_tri(int x,int y,int k,int d)
{
long long ans=0;
int i;
for (i=0;i<k;i++)
{
if (d==1)
{
ans+=calc_line(x,y,y+i);
}
else
{
ans+=calc_line(x,y-i,y);
}
x+=d;
}
return ans;
}
void calc_tri(int x,int y,int k,int d)
{
if (k%(2*l)==0)
{
ans+=(long long)calc_small_tri(x,y,2*l,d)*(k/(2*l));
if (d==1)
{
ans+=sum(x+2*l,y,x+4*l-1,y+2*l-1,0)*(long long)(k/(2*l))*((k/(2*l))-1)/2;
}
else
{
ans+=sum(x-4*l+1,y-2*l+1,x-2*l,y,0)*(long long)(k/(2*l))*((k/(2*l))-1)/2;
}
return;
}
else
{
k--;
if (d==1)
{
ans+=calc_line(x+k,y,y+k);
}
else
{
ans+=calc_line(x-k,y-k,y);
}
calc_tri(x,y,k,d);
return;
}
}
int main()
{
int t;
scanf("%d",&t);
int zu;
for (zu=0;zu<t;zu++)
{
scanf("%d",&l);
L2=l*2;
L=l;
int i;
for (i=0;i<l;i++)
{
scanf("%d",&a[i]);
}
int q;
scanf("%d",&q);
for (i=0;i<q;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int len1=x2-x1+1;
int len2=y2-y1+1;
x1+=y1;
y1=x1-y1;
x2+=y2;
y2=x2-y2;
int k=min(len1,len2);
k--;
ans=0;
calc_tri(x1,y1,k,1);
calc_tri(x2,y2,k,-1);
x1+=k;
x2-=k;
int tag;
if (len1>len2)
{
tag=1;
}
else
{
tag=0;
}
ans+=sum(x1,y1,x2,y2,tag);
cout<<ans<<'
';
}
}
return 0;
}
J
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define rotate asdi021jdcoaise021jl
char c[25][25];
int a[25][25];
int vis_line[25][25];
int vis_col[25][25];
int rotate[5][5];
int ans=10000;
void get_rotate(int x,int y)
{
static int b[5][5];
int i;
for (i=0;i<4;i++)
{
int j;
for (j=0;j<4;j++)
{
b[i][j]=a[i+x*4][j+y*4];
}
}
for (i=0;i<4;i++)
{
int j;
for (j=0;j<4;j++)
{
a[j+x*4][3-i+y*4]=b[i][j];
}
}
}
bool check_valid(int x,int y)
{
int i,j;
for (i=x*4;i<x*4+4;i++)
{
for (j=y*4;j<y*4+4;j++)
{
if (vis_line[i][a[i][j]])
{
return false;
}
if (vis_col[j][a[i][j]])
{
return false;
}
}
}
return true;
}
void get_valid(int x,int y,int c)
{
int i,j;
for (i=x*4;i<x*4+4;i++)
{
for (j=y*4;j<y*4+4;j++)
{
vis_line[i][a[i][j]]+=c;
vis_col[j][a[i][j]]+=c;
}
}
}
void dfs(int x,int y)
{
if (y==4)
{
dfs(x+1,0);
return;
}
if (x==4)
{
int i,j;
int k;
int sum=0;
for (i=0;i<4;i++)
{
for (j=0;j<4;j++)
{
sum+=(rotate[i][j])%4;
}
}
ans=min(ans,sum);
return;
}
rotate[x][y]=0;
int k;
for (k=0;k<4;k++)
{
if (check_valid(x,y))
{
get_valid(x,y,1);
dfs(x,y+1);
get_valid(x,y,-1);
}
get_rotate(x,y);
rotate[x][y]++;
}
}
void find_solution()
{
rotate[0][0]=0;
/*get_valid(0,0,1);
dfs(0,1);
get_valid(0,0,-1);
*/
dfs(0,0);
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t;
scanf("%d",&t);
int zu;
for (zu=0;zu<t;zu++)
{
int i;
for (i=0;i<16;i++)
{
scanf("%s",c[i]);
}
int j;
for (i=0;i<16;i++)
{
for (j=0;j<16;j++)
{
if (c[i][j]<='9')
{
a[i][j]=c[i][j]-'0';
}
else
{
a[i][j]=c[i][j]-'A'+10;
}
}
}
ans=10000;
find_solution();
printf("%d
",ans);
}
return 0;
}
K
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[505];
void fail()
{
puts("IMPOSSIBLE");
}
void try_ans()
{
int n=strlen(a);
int i;
int num=-1;
for (i=0;i<n;i++)
{
if (a[i]=='0')
{
if (num==-1)
{
num=0;
}
else if (num==0)
{
fail();
return;
}
}
else if ((a[i]=='+')||(a[i]=='*'))
{
if (num==-1)
{
fail();
return;
}
num=-1;
}
else if (a[i]=='?')
{
if (num==0)
{
a[i]='+';
num=-1;
}
else
{
a[i]='1';
num=1;
}
}
else
{
if (num!=0)
{
num=1;
}
else
{
fail();
return;
}
}
}
if (num==-1)
{
fail();
return;
}
printf("%s
",a);
}
int main()
{
int t;
scanf("%d",&t);
int i;
for (i=0;i<t;i++)
{
scanf("%s",a);
try_ans();
}
return 0;
}
L
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
int zu;
for (zu=0;zu<t;zu++)
{
int n;
scanf("%d",&n);
int i;
int p;
for (i=0;i<n;i++)
{
int x;
scanf("%d",&x);
if (i==0)
{
p=x;
}
if (i==n-1)
{
p-=x;
}
}
printf("%d
",(int)sqrt(abs(p)));
}
return 0;
}