A、试题类型：
送分题。
B、算法模型：
基本推理。
C、试题说明：
绘制表找规律。
ans=a*b-(a+b)
ans=a∗b−(a+b)
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
long long a,b,ans;
scanf("%lld%lld",&a,&b);
ans=a*b-a-b;
printf("%lld",ans);
return 0;
}
A、试题类型：
复杂度。
B、算法模型：
多循环。
C、试题说明：
关于循环的复杂度问题。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,l,zz,mm,ans,fl,num1,sum1,sum2,tot=0,x,y;
string s,s1,s2;
char ch,chan[105]={};
bool psx[100]={},flag;
void clean()
{
flag = 1;//判断代码是否ERR，0是错误，1是正确
num1 = 0;//记录小明自己的结果
zz=0;//循环没有结束时记录复杂度的暂时容器
mm=0;//记入有效但是不计入zz的常数到常数循环，防止将zz错减
ans=0;//正确的复杂度
fl=0;//判断没有进入的循环
sum1=0;//F的数量
sum2=0;//E的数量
memset(psx,0,sizeof(psx));//用过的变量名
tot = 0;
}
int main()
{
//freopen("complexity.in","r",stdin);
//freopen("complexity.out","w",stdout);
cin>>t;
while(t--)
{
clean();
cin>>l>>s;
if(l % 2)
flag = 0;//如果代码长度是奇数，那么F与E的数量一定不一样，错误
if(s.size() == 4)
num1 = 0;//O（1）的情况
else
for(int i = 4; i < s.size()-1; i++)
num1 = num1 * 10 + int(s[i] - '0');
//因为w小于100，所以要用循环，我就摔在这
while(l--)
{
cin>>ch;
if(ch == 'F')
{
sum1++;
cin>>chan[++tot];//因为循环一层层退出，所以字母要有顺序
if(psx[chan[tot]-'a'+1] == 1)
flag = 0;//如果字母已出现，程序错误
psx[chan[tot]-'a'+1] = 1;//记录字母
cin>>s1>>s2;//输入字符串，因为x和y有可能是n，不能用int，char读不尽
if(!flag)
continue;//输入的都输入了，如果程序错误，退出继续输入
if(fl)
{
fl++;continue;
}//如果上一层循环没有进入，那么这一层也一定没有进
if(s1[0] == 'n' && s2[0] != 'n')
{
fl++;
continue;
}//因为n远大于吗100，循环不进去
if(s1[0] != 'n' && s2[0] == 'n')
zz++;//出现一层n，zz++（这里的1是指n的次方加一）
if(s1[0] != 'n' && s2[0] != 'n')
{//如果两个常数
if(s1.size() > s2.size())
{
fl++;
continue;
}//不进入循环
mm++;
if(s1.size() == s2.size())
for(int i = 0; i < s1.size(); i++)
{
if(s1[i] > s2[i])
{
mm--;
fl++;
continue;
}
if(s1[i] < s2[i])
break;
}//比较大小，因为数不是一位数，要循环
}
}
if(ch == 'E')
{
if(!flag)
continue;//如果程序错误退出
sum2++;
psx[chan[tot--]-'a'+1] = 0;//字母可以用了
if(fl)
{
fl--;
continue;
}//如果程序没有进入的，就往外退
if(zz > 0)
{
ans = max(ans,zz);!mm ? zz-- : mm--;
}
//如果zz大于0，就更新ans，只是退出一层循环，所以zz--，而不是清零
}
}
if(!flag || sum1 != sum2 || fl)
printf("ERR\n");
//如果程序错误，E和F数量不一样，没进入的程序还没有退出完
else if(ans == num1)
printf("Yes\n");//如果小明答案和正确答案一样
else
printf("No\n");
}
return 0;
}
A、试题类型：
路径问题。
B、算法模型：
最短路 + 拓扑序 + dp。
C、试题说明：
无。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 200005,maxm = 400005,maxk = 60,INF = 1000000000;
inline int read()
{
int out = 0,flag = 1;char c = getchar();
while (c < 48 || c > 57)
{
if (c == '-')
flag = -1; c = getchar();
}
while (c >= 48 && c <= 57)
{
out = out * 10 + c - 48; c = getchar();
}
return out * flag;
}
int N,M,K,P;
int dS[maxn],dT[maxn],f[maxn][maxk],inde[maxn],id[maxn];
bool vis[maxn],zer[maxn];
int head[maxn],nedge = 0,h[maxn],ne = 0;
struct EDGE
{
int to,w,next;
}edge[maxm],e[maxm];
inline void build(int u,int v,int w)
{
edge[nedge] = (EDGE)
{
v,w,head[u]
};
head[u] = nedge++;
e[ne] = (EDGE)
{
u,w,h[v]
};
h[v] = ne++;
if (!w)
zer[u] = zer[v] = true,inde[v]++;
}
struct node
{
int u,d;
};
inline bool operator <(const node& a,const node& b)
{
return a.d > b.d;
}
struct Node
{
int d,ti;
}E[maxn];
inline bool cmp(const int& a,const int& b)
{
return E[a].d == E[b].d ? E[a].ti < E[b].ti : E[a].d < E[b].d;
}
void dijkstraS()
{
REP(i,N) dS[i] = INF,vis[i] = false;
priority_queue<node> q;
dS[1] = 0;
q.push((node){1,dS[1]});
node u; int to;
while (!q.empty()){
u = q.top();
q.pop();
if (vis[u.u])
continue;
vis[u.u] = true;
Redge(u.u)
if (!vis[to = edge[k].to])
{
if (dS[to] >= dS[u.u] + edge[k].w)
{
dS[to] = dS[u.u] + edge[k].w;
q.push((node){to,dS[to]});
}
}
}
}
void dijkstraT()
{
REP(i,N) dT[i] = INF,vis[i] = false;
priority_queue<node> q;
dT[N] = 0;
q.push((node){N,dT[N]});
node u; int to;
while (!q.empty())
{
u = q.top();
q.pop();
if (vis[u.u]) continue;
vis[u.u] = true;
for (int k = h[u.u]; k != -1; k = e[k].next)
if (!vis[to = e[k].to] && dT[to] > dT[u.u] + e[k].w)
{
dT[to] = dT[u.u] + e[k].w;
q.push((node){to,dT[to]});
}
}
}
bool tuopu()
{
queue<int> q;
REP(i,N)
{
id[i] = i;
E[i].d = dS[i]; E[i].ti = 0;
if (zer[i] && !inde[i])
{
q.push(i);
}
}
int u,to,cnt = 0;
while (!q.empty())
{
u = q.front();
q.pop();
E[u].ti = ++cnt;
Redge(u) if (!edge[k].w)
{
inde[to = edge[k].to]--;
if (!inde[to])
q.push(to);
}
}
REP(i,N) if (zer[i] && inde[i] && dS[i] + dT[i] <= dT[1] + K)
{
printf("-1\n");
return false;
}
sort(id + 1,id + 1 + N,cmp);
//REP(i,N) cout<<id[i]<<' ';cout<<endl;
return true;
}
void solve()
{
dijkstraS();
dijkstraT();
//REP(i,N) cout<<f[i][0]<<' ';cout<<endl;
if(!tuopu())
return;
f[1][0] = 1;
for (int j = 0; j <= K; j++)
for (int i = 1; i <= N; i++)
{
int u = id[i];
Redge(u){
int v = edge[k].to;
if (dS[u] + j + edge[k].w - dS[v] <= K){
f[v][dS[u] + j + edge[k].w - dS[v]] = (f[v][dS[u] + j + edge[k].w - dS[v]] + f[u][j]) % P;
}
}
}
int ans = 0;
for (int i = 0; i <= K; i++)
ans = (ans + f[N][i]) % P;
printf("%d\n",ans);
}
void init()
{
int a,b,c;
memset(f,0,sizeof(f));
N = read(); M = read(); K = read(); P = read();
ne = nedge = 0;
REP(i,N) head[i] = h[i] = -1,inde[i] = 0,zer[i] = false;
while (M--)
{
a = read();
b = read();
c = read();
build(a,b,c);
}
}
int main()
{
int T = read();
while (T--)
{
init();
solve();
}
return 0;
}
A、试题类型：
集合问题。
B、算法模型：
维护并查集。
C、试题说明：
无。
#include <cstdio>
#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
ll T,n;
double h,r,low,high;
int f[1010];
struct ball
{
double x,y,z;
}s[1010];
double dist(ball a,ball b)
{
double x=a.x-b.x,y=a.y-b.y,z=a.z-b.z;
return sqrt(x*x+y*y+z*z);
}
int getf(int x)
{
if (f[x]==x) return x;
return f[x]=getf(f[x]);
}
void Union(int x,int y)
{
x=getf(x);
y=getf(y);
if (x!=y) f[y]=f[x];
}
int main()
{
scanf("%lld",&T);
while (T--)
{
scanf("%lld%lf%lf",&n,&h,&r);
low=h;high=0;
for (int i = 1;i <= n;i++)
{
scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].z);
low=min(low,s[i].z);
high=max(high,s[i].z);
}
if (low-r>0||high+r<h)
{
printf("No\n");
continue;
}
for (int i = 0;i <= n+1;i++) f[i]=i;
for (int i = 1;i <= n;i++)
{
if (s[i].z-r<=0) Union(0,i);
if (s[i].z+r>=h) Union(i,n+1);
}
for (int i = 1;i < n;i++)
for (int j = i+1;j <= n;j++)
if (dist(s[i],s[j])<=2*r)
Union(i,j);
if (getf(0)==getf(n+1))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
A、试题类型：
基本算法。
B、算法模型：
DP。
C、试题说明：
枚举起点，再向下dp。
枚举集合的子集 for(int i=s;i;i=(i-1)&s)。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=15;
int n,m;
long long g[MAXN][MAXN];
long long f[MAXN][1<<12],d[MAXN][1<<12],D[1<<12][1<<12];
long long ans=0x7f7f7f7f;
int main()
{
cin>>n>>m;
memset(g,0x7f,sizeof(g));
for(int i=1;i<=m;i++)
{
int u,v;
long long l;
scanf("%d%d%lld",&u,&v,&l);
g[u][v]=min(g[u][v],l);
g[v][u]=min(g[v][u],l);
}
memset(d,0x7f,sizeof(d));
int u=(1<<n)-1;
for(int i=1;i<=n;i++)
{
for(int s=0;s<(1<<n);s++)
{
for(int j=1;j<=n;j++)
if((s>>(j-1))&1)
{
d[i][s]=min(d[i][s],g[j][i]);
}
}
}
for(int s=0;s<(1<<n);s++)
for(int S=s^u;S;S=(S-1)&(s^u))
for(int i=1;i<=n;i++)
if((S>>(i-1))&1)
{
if(d[i][s]==d[0][0])
{
D[s][S]=0;
break;
}
D[s][S]+=d[i][s];
}
for(int r=1;r<=n;r++)
{
memset(f,0x7f,sizeof(f));
f[1][1<<(r-1)]=0;
for(int i=2;i<=n;i++)
for(int s=0;s<(1<<n);s++)
for(int S=s^u;S;S=(S-1)&(s^u))
if(f[i-1][s]!=f[0][0]&&D[s][S])
f[i][s|S]=min(f[i][s|S],f[i-1][s]+D[s][S]*(i-1));
for(int i=1;i<=n;i++)
ans=min(ans,f[i][(1<<n)-1]);
}
cout<<ans;
return 0;
}
A、试题类型：
典型数据结构。
B、算法模型：
树。
C、试题说明：
用平衡树与树状数组应用。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define ls tr[x].son[0]
#define rs tr[x].son[1]
#define LL long long
using namespace std;
template<typename T> inline void read(T &x)
{
x = 0;
int f = 0;
char s = getchar();
while (s < '0' || '9' < s)
f |= s == '-', s = getchar();
while ('0' <= s && s <= '9')
x = x * 10 + s - 48, s = getchar();
x = f ? -x : x;
}
const int N = 3e5 + 10;
struct node
{
int f, d, p, son[2], dat;
} tr[N << 1]; int len, rt[N];
void update(int x)
{
tr[x].dat = tr[ls].dat + tr[rs].dat + tr[x].d;
}
void rotate(int x)
{
int f = tr[x].f, ff = tr[f].f, w = (tr[f].son[1] == x), r, R;
r = tr[x].son[1 - w], R = f;
tr[R].son[w] = r;
if (r)
tr[r].f = R;
r = x, R = ff;
if (R)
tr[R].son[tr[ff].son[1] == f] = r;
tr[r].f = R;
r = f, R = x;
tr[R].son[1 - w] = r;
tr[r].f = R;
update(f);
update(x);
}
void splay(int x, int h)
{
int f, ff;
while (tr[x].f)
{
f = tr[x].f, ff = tr[f].f;
if (ff)
(tr[ff].son[1] == f) ^ (tr[f].son[1] == x) ? rotate(x) : rotate(f);
rotate(x);
}
rt[h] = x;
}
void insert(int h, int p, int siz)
{
int x = rt[h];
while (1)
{
if (p < tr[x].p)
{
if (ls) x = ls;
else
{
tr[++len] = (node){x, siz, p, {0, 0}, siz};
tr[x].son[0] = len;
splay(len, h);
break;
}
}
else
{
if (rs) x = rs;
else
{
tr[++len] = (node){x, siz, p, {0, 0}, siz};
tr[x].son[1] = len;
splay(len, h);
break;
}
}
}
}
int findip(int h, int l)
{
int x = rt[h];
while (x)
{
if (tr[ls].dat + tr[x].d < l) l -= tr[ls].dat + tr[x].d, x = rs;
else if (l <= tr[ls].dat) x = ls;
else
{
l -= tr[ls].dat;
int now = tr[x].p + l, tt = tr[x].d;
tr[x].d = l - 1; update(x);
l = tt - l;
splay(x, h);
insert(h, now, l);
return now;
}
}
return -l;
}
int n, m, q, c[N << 1], cnt[N], c1[N], cs[N]; LL num[N << 1], num1[N];
void change(int x, int w)
{
for (; x <= n + q; x += x & -x)
c[x] += w;
}
int qx[N], qy[N], ac[N];
int main()
{
freopen("P3960.in", "r", stdin);
freopen("P3960.out", "w", stdout);
read(n), read(m), read(q);
for (int i = 1; i <= n; i++)
{
rt[i] = ++len;
tr[len] = (node){0, m - 1, 0, {0, 0}, m - 1};
num[i] = 1ll * i * m;
}
for (int i = 1; i <= n + q; i++)
c[i] = i & -i;
for (int i = 1; i <= q; i++)
{
read(qx[i]), read(qy[i]);
cnt[qx[i]]++;
}
cnt[n + 1] = q + 1;
for (int i = n; i >= 1; i--)
{
cs[i] = log(cnt[i]) / log(2);
cnt[i] = cnt[i + 1] - cnt[i];
}
for (int i = 1; i <= n; i++)
for (int j = cnt[i]; j < cnt[i + 1]; j++)
c1[j] = (j - cnt[i] + 1) & -(j - cnt[i] + 1);
int t = log(n + q) / log(2);
for (int i = 1; i <= 93; i++)
{
// printf("%d\n", i);
int h, l;
h = qx[i];
l = qy[i];
int pos = 0, sum = 0;
for (int j = t; j >= 0; j--)
if (pos + (1 << j) <= n + i - 1 && sum + c[pos + (1 << j)] < h)
sum += c[pos + (1 << j)], pos += (1 << j);
pos++;
num1[cnt[h] + ac[h]] = num[pos]; ac[h]++;
change(pos, -1);
int now = findip(h, l);
if (now > 0)
{
num[n + i] = 1ll * (h - 1) * m + (LL)now; printf("%lld\n", num[n + i]);
}
else
{
now = -now;
pos = cnt[h] - 1, sum = 0;
for (int j = cs[h]; j >= 0; j--)
if (pos + (1 << j) < cnt[h + 1] && sum + c1[pos + (1 << j)] < now)
sum += c1[pos + (1 << j)], pos += (1 << j);
pos++;
for (int j = pos; j < cnt[h + 1]; j += (j - cnt[h] + 1) & -(j - cnt[h] + 1)) c1[j]--;
printf("%lld\n", num1[pos]);
num[n + i] = num1[pos];
}
}
for (int i = 94; i <= q; i++)
{
// printf("%d\n", i);
int h, l;
h = qx[i];
l = qy[i];
int pos = 0, sum = 0;
for (int j = t; j >= 0; j--)
if (pos + (1 << j) <= n + i - 1 && sum + c[pos + (1 << j)] < h)
sum += c[pos + (1 << j)], pos += (1 << j);
pos++;
num1[cnt[h] + ac[h]] = num[pos]; ac[h]++;
change(pos, -1);
int now = findip(h, l);
if (now > 0)
{
num[n + i] = 1ll * (h - 1) * m + (LL)now; printf("%lld\n", num[n + i]);
}
else
{
now = -now;
pos = cnt[h] - 1, sum = 0;
for (int j = cs[h]; j >= 0; j--)
if (pos + (1 << j) < cnt[h + 1] && sum + c1[pos + (1 << j)] < now)
sum += c1[pos + (1 << j)], pos += (1 << j);
pos++;
for (int j = pos; j < cnt[h + 1]; j += (j - cnt[h] + 1) & -(j - cnt[h] + 1))
c1[j]--;
printf("%lld\n", num1[pos]);
num[n + i] = num1[pos];
}
}
return 0;
}
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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
