A、试题类型：
逻辑推理。
B、算法模型：
拓扑排序。
C、试题说明：
涉及到分数的加法。
如果开了long long，且分数相加时分母取LCM先除后乘，90分。
如果先乘后除，或者分数相加时分母直接相乘， 只可以得到60分。
可以写一个两位数的高精度，或者用long double，注意运算时的精度。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 100010
#define M 500010
#define ld long double
#define e 0.000000000001
int last[N], nxt[M * 2], to[M * 2], len = 0;
int d0[N], d[N];
int q[N];
struct
{
ld x, y;
}s[N];
void add(int x, int y)
{
to[++len] = y;
nxt[len] = last[x];
last[x] = len;
}
ld fl(ld x)
{
ld y = floor(x);
if(y + 1.0 - e <= x)
y++;
return y;
}
ld gcd(ld x, ld y)
{
return (y >= -e && y <= e) ? x : gcd(y, x - fl(x / y) * y);
}
int main()
{
int n, m, i, j, x, y;
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++)
{
scanf("%d", &d0[i]);
for(j = 1; j <= d0[i]; j++)
scanf("%d", &x), d[x]++, add(i, x);
}
int l = 0, r = 0;
for(i = 1; i <= n; i++) s[i].y = 1;
for(i = 1; i <= n; i++) if(!d[i])
q[++r] = i, s[i].x = 1;
int tt = 0;
while(l < r)
{
x = q[++l];
for(int i = last[x]; i; i = nxt[i])
{
y = to[i];
ld X = s[x].x, Y = s[x].y * d0[x];
ld g = gcd(s[y].y, Y);
s[y].x = s[y].y / g * X + Y / g * s[y].x;
s[y].y = s[y].y / g * Y;
d[y]--;
if(!d[y])
q[++r] = y;
}
}
for(i = 1; i <= n; i++) if(!d0[i])
{
ld g = gcd(s[i].x, s[i].y);
printf("%.0Lf %.0Lf\n", s[i].x / g, s[i].y / g);
}
return 0;
}
A、试题类型：
字符串经典问题。
B、算法模型：
hash算法。
C、试题说明：
在循环查找一共AB可以循环多少次时，直接调用hash，就可以免除查找很多次。
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ULL unsigned long long
#define HASH 13331
#define int long long
using namespace std;
const int MAXN = 1e6 + 5;
const int MAXC = 1e2 + 5;
int t,len,q[MAXC],cnt[MAXN],ans,C,Bit[MAXC];
ULL id[MAXN],Hash[MAXN];
char s[MAXN];
ULL _Hash(int l,int r)
{
return Hash[r] - Hash[l - 1] * id[r - l + 1];
}
int lowbit(int x)
{
return x & (-x);
}
int Sum(int x)
{
int res = 0;
for(;x;x -= lowbit(x))
res += Bit[x];
return res;
}
void Update(int x,int y)
{
for(;x <= 26;x += lowbit(x))
Bit[x] += y;
}
signed main()
{
scanf("%lld",&t);
while(t --)
{
scanf("%s",s + 1);
len = strlen(s + 1);
memset(Hash,0,sizeof(Hash));
memset(id,0,sizeof(id));
memset(q,0,sizeof(q));
memset(cnt,0,sizeof(cnt));
memset(Bit,0,sizeof(Bit));
ans = 0,C = 1;
id[0] = 1;
for(int i = 1;i <= len;i ++)
{
Hash[i] = Hash[i - 1] * HASH + s[i] - 'a' + 1;
id[i] = id[i - 1] * HASH;
}
for(int i = len;i >= 1;i --)
{
q[s[i] - 'a'] ++;
if(q[s[i] - 'a'] % 2) cnt[i] = cnt[i + 1] + 1;
else cnt[i] = cnt[i + 1] - 1;
// printf("%lld\n",cnt[i]);
}
memset(q,0,sizeof(q));
Update(2ll,1ll);
q[s[1] - 'a'] ++;
for(int i = 2;i < len;i ++)
{
ULL num1 = Hash[i];
int cyc = 1;
for(int j = i + 1;j + i - 1 < len;j += i)
{
if(_Hash(j,j + i - 1) != num1) break;
cyc ++;
}
int k = cyc - 1;
// printf("%lld\n",cyc);
if(k % 2)
ans += (1 + (k - 1) / 2) * Sum(cnt[i * cyc + 1] + 1) + (k + 1) / 2 * Sum(cnt[i * (cyc - 1) + 1] + 1);
else
ans += (k / 2 + 1) * Sum(cnt[i * cyc + 1] + 1) + k / 2 * Sum(cnt[i * (cyc - 1) + 1] + 1);
q[s[i] - 'a'] ++;
if(q[s[i] - 'a'] % 2)
C ++;
else
C --;
Update(C + 1,1);
// printf("%lld\n",ans);
}
printf("%lld\n",ans);
}
return 0;
}
A、试题类型：
典型思想问题。
B、算法模型：
分治思想。
C、试题说明：
分治思想：首先考虑只有两种颜色的情况：
考虑将所有黑色的球移动到白色的球上方。具体来说：先将要操作的柱子找出来，找到其里面有多少个黑球（设有k个），将随便另外一个柱子最上方的k个球移到空柱上，然后操作这个柱子，将黑球移到选的柱子上，白球移到空柱上，再将黑球和白球先后移会来，每时每刻空余位置数都是m，所以是合法的。
然后考虑将每种颜色的球移动到一个柱子上。可以考虑对于每一个要操作的柱子，找到另外一个要操作的柱子，分黑球数之和大于m和小于m来讨论，就可以容易实现。
对于n>2n>2的情况，可以考虑分治，将所有球染为黑白两色，同颜色的也染为同颜色，然后给这些球各自分配一半的柱子，然后继续递归下去就可以解决了。大概计算一下，总共的移球次数是在800000左右。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 60
#define M 500
using namespace std;
int n,m,i,j,c[N][M],ans,ans1[1000000][3],num,id[M],cnt[N];
int read()
{
int x=0;
char ch=getchar();
while (ch>'9'||ch<'0') ch=getchar();
while (ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
void move(int x,int y,int num)
{
int i;
for (i=1;i<=num;i++)
{
cnt[x]--;cnt[y]++;
c[y][cnt[y]]=c[x][cnt[x]+1];c[x][cnt[x]+1]=0;
ans++;
ans1[ans][1]=x;ans1[ans][2]=y;
}
}
void dfs(int l,int r)
{
int mid=(l+r)/2,i,j,sum,x,y,s1,s2;
if (l==r)
return;
num=0;
for (i=1;i<=n;i++)
if (c[i][1]>=l&&c[i][2]<=r)
id[++num]=i;
for (i=1;i<=num;i++){
sum=0;
x=id[i];y=id[i%num+1];
for (j=1;j<=m;j++)
if (c[x][j]>=l&&c[x][j]<=mid)
sum++;
if (!sum)
continue;
move(y,n+1,sum);
s1=s2=0;
for (j=m;j>=1;j--)
{
if (s1>=sum)
break;
if (c[x][j]>=l&&c[x][j]<=mid)
{
s1++;
move(x,y,1);
}
else
{
s2++;
move(x,n+1,1);
}
}
move(n+1,x,s2);
move(y,x,s1);
move(n+1,y,s1);
}
for (i=1;i<=num-1;i++)
{
x=id[i];y=id[i%num+1];
s1=s2=0;
for (j=1;j<=m;j++)
{
if (c[x][j]>=l&&c[x][j]<=mid)
s1++;
if (c[y][j]>=l&&c[y][j]<=mid)
s2++;
}
if (s1==m||s1==0)
continue;
if (s1+s2>m)
{
move(x,n+1,m);
move(y,x,s2);
move(n+1,y,m-s1);
move(n+1,x,m-s2);
move(n+1,y,cnt[n+1]);
}
else
{
move(x,n+1,s1);
move(y,n+1,s2);
move(y,x,s1);
move(n+1,y,s1+s2);
}
}
dfs(l,mid);dfs(mid+1,r);
}
int main()
{
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
n=read();m=read();
for (i=1;i<=n;i++)
{
cnt[i]=m;
for (j=1;j<=m;j++)
c[i][j]=read();
}
dfs(1,n);
printf("%d\n",ans);
for (i=1;i<=ans;i++)
printf("%d %d\n",ans1[i][1],ans1[i][2]);
return 0;
}
A、试题类型：
经典数学问题联合题。
B、算法模型：
幂和，用拉格朗日插值计算就行。暴力卷出。
C、试题说明：
无。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define mod 1000000007
int n,k,w[11],ans=0;
int d[11];
int l[500010][11],r[500010][11];
void add(int &x,int y)
{
x=(x+y>=mod?x+y-mod:x+y);
}
void dec(int &x,int y)
{
x=(x-y<0?x-y+mod:x-y);
}
struct Poly
{
int a[11],t;
Poly()
{
t=0;memset(a,0,sizeof(a));
}
void clear()
{
t=0;
memset(a,0,sizeof(a));
}
void operator *=(Poly &B)
{
Poly re;re.t=t+B.t;
for(int i=0;i<=t;i++)
for(int j=0;j<=B.t;j++)
add(re.a[i+j],1ll*a[i]*B.a[j]%mod);
*this=re;
}
}s[11];
int t_max=1e9;
int calc_round_1()
{//暴力求解第一轮
int re=0;
for(int i=1;i<=n;i++)
{
int prod=1;
for(int j=1;j<=k;j++)
if(w[j]-r[i][j]+l[i][j]>0)
prod=1ll*prod*(w[j]-r[i][j]+l[i][j])%mod;
else
{
prod=0;
break;
}
add(re,prod);
}
return re;
}
int calc_round_t_max_and_1()
{//暴力求解最后一轮
int re=0;
for(int i=1;i<=n;i++)
{
int prod=1;
for(int j=1;j<=k;j++)
{
int p=w[j]-max(r[n][j],r[i][j]+d[j])+min(l[n][j],l[i][j]+d[j])-(t_max+1)*abs(d[j]);
if(p>0)
prod=1ll*prod*p%mod;
else
{
prod=0;
break;
}
}
add(re,prod);
}
return re;
}
int ksm(int x,int y)
{
int re=1;
for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);
return re;
}
struct Lagrange
{//自然数幂和板子
int fac[20],inv_fac[20];
Lagrange()
{
}
void init()
{
fac[0]=inv_fac[0]=1;
for(int i=1;i<=15;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv_fac[15]=ksm(fac[15],mod-2);
for(int i=14;i>=1;i--)inv_fac[i]=1ll*inv_fac[i+1]*(i+1)%mod;
}
int pre[20],suf[20];
int calc(int k,int x)
{
if(!k)
return x+1;
int re=0,sum=0;
if(x<=k+2)
{
for(int i=0;i<=x;i++)add(re,ksm(i,k));
return re;
}
pre[0]=1;
for(int i=1;i<=k+2;i++)
pre[i]=1ll*pre[i-1]*(x-i)%mod;
suf[k+3]=1;
for(int i=k+2;i>=1;i--)
suf[i]=1ll*suf[i+1]*(x-i)%mod;
for(int i=1;i<=k+2;i++)
{
add(sum,ksm(i,k));
(k+2-i&1?dec:add)(re,1ll*sum*pre[i-1]%mod*suf[i+1]%mod
*inv_fac[i-1]%mod*inv_fac[k+2-i]%mod);
}
return re;
}
}Lag;
int cd[20];
int main()
{
scanf("%d %d",&n,&k);ans=1;
for(int i=1;i<=k;i++)
scanf("%d",&w[i]),ans=1ll*ans*w[i]%mod;
for(int i=1,x,y;i<=n;i++)
{
scanf("%d %d",&x,&y);
d[x]+=y;
for(int j=1;j<=k;j++)
l[i][j]=min(l[i-1][j],d[j]),
r[i][j]=max(r[i-1][j],d[j]);
}
bool tf=false;//判无解
for(int i=1;i<=k;i++)
if(l[n][i]+r[n][i]>=w[i]||d[i]!=0)tf=true;
if(!tf)return puts("-1"),0;
for(int i=1;i<=k;i++)//求t_max
if(w[i]-r[n][i]+l[n][i]<=0){t_max=-2;break;}
else if(d[i]!=0)t_max=min(t_max,(w[i]-r[n][i]+l[n][i])/abs(d[i])-1);
add(ans,calc_round_1());
if(t_max>-2)add(ans,calc_round_t_max_and_1());
if(t_max>=0)
{
Lag.init();//预处理自然数幂和
for(int i=0;i<=k;i++)
cd[i]=Lag.calc(i,t_max);
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++)
{
s[j].clear();//计算出所有多项式，暴力乘起来
s[j].t=d[j]!=0;
s[j].a[0]=w[j]-max(r[n][j],r[i][j]+d[j])+min(l[n][j],l[i][j]+d[j]);
s[j].a[1]=(mod-abs(d[j]))%mod;
if(j>1)
s[j]*=s[j-1];
}
for(int j=0;j<=k;j++)
add(ans,1ll*s[k].a[j]*cd[j]%mod);
}
}
printf("%d",ans);
}
IT航班提供：教辅资料、课程视频、课程书籍、竞赛辅导、少儿编程指导、课程采购、加盟、少儿编程资料、少儿编程课程、保送生、特长生、加分、中小学计算机教育、中小学信息学、竞赛、中小学信息学课程、人工智能、中小学编程加盟、少儿编程加盟、品牌加盟、技术加盟、技术指导、课程加盟、师资培训、中小学编程教辅资料、中小学编程教师培训、少儿编程教学书籍、少儿编程视频、教学书籍、教师培训、教学视频、CSP-J/S、中小学信息学课程服务、竞赛指导、课程提供、国内外计算机中小学计算机竞赛、信息学竞赛、信息学课程提供商、信息学奥林匹克。
IT航班支持----中小学编程比赛汇总：
第一部分：国内比赛(IT航班支持)
1、软件能力认证(CSP-JS)
2、全国青少年信息学奥林匹克联赛(NOIP)
3、全国青少年信息学奥林匹克竞赛(NOI)
4、中国青少年………………………
5、………………………创新挑战赛
6、全国青少年………………………
7、………………………
8、 恩欧希教育信息化发明创新奖
9、世界机器人大赛(WRC)
10、………………………大赛
11、少………………………智能教育成果展示大赛
12、“明天小小科学家”奖励活动
13、………………………
14、………………………
15、国际信息学………………………
16、………………………
第二部分：国际比赛(IT航班支持)
17、………………………
18、国际………………………
19、………………………
20、美国信息学………………………
21、加拿大………………………
22、官方邀请赛 (CCO)
23、国际计算思维………………………
24、美国计算机………………………
25、澳大利亚………………………
第三部分：企业比赛(IT航班支持)
26、微软MTA
27、………………………挑战赛
28、………………………科学奖
29、………………………学奖
30、………………………创新挑战赛
31、………………………挑战赛
32、………………………芯计算机表演赛
33、………………………大赛
第四部分：Scratch相关竞赛(IT航班支持)
34、全国中小学生电脑制作大赛
35、………………………
36、………………………
37、………………………
第五部分：其它(IT航班支持)
38、NOI夏令营
39、NOI冬令营(NOIWC)
40、全国青少年………………………
41、国际青少年………………………
联系方式：
A、官方网址：
B、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
