A-口算题

#include<cstdio>
#include<algorithm>
using namespace std;
int a[110],n,ans;
bool book[20010];
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<n; i++) for(int j=i+1; j<=n; j++) book[a[i]+a[j]]=1;//标记所有可能的和
for(int i=1; i<=n; i++) if(book[a[i]]) ans++;
printf("%d",ans);
return 0;
}

B-幸运数

#include<bits/stdc++.h>
using namespace std;
int nex[10010];
bool book[10010];//判断一个数是否被区间内的其他数字所经过
int lucky[10010];//判断一个数是否为幸运数，如果是的话经过了多少个数字
int dfs(int x) //递归求一个数变为1的过程中经过的数字个数
{
if(x==1||lucky[x]!=0) return lucky[x];
lucky[x]=-1; //初始化为-1，防止形成死循环
int tmp=dfs(nex[x]);
if(tmp!=-1) lucky[x]=tmp+1;
//如果tmp为-1，表示形成了死循环；否则，返回的是经过的数字个数
return lucky[x];
}
int main()
{
int l,r;
cin>>l>>r;
for(int i=1;i<=10000;i++)
{
int x=i;
int y=0;
while(x)
{
int tmp=x%10;
y+=tmp*tmp;
x/=10;
}
nex[i]=y;
if(i>=l&&i<=r) book[y]=1;
}
for(int i=2;i<=10000;i++) dfs(i);
bool flag=0;
for(int i=l;i<=r;i++)
{
if(book[i]==0&&lucky[i]!=-1) //是特殊的幸运数
{
flag=1;
int x=lucky[i]; //初始化幸运度为经过的数字个数
bool zs=1;
for(int j=2;j*j<=i;j++)
{
if(i%j==0)
{
zs=0;
break;
}
}
if(zs) x*=2;
cout<<i<<' '<<x<<endl;
}
}
if(flag==0) cout<<"SAD";
return 0;
}

C-接金币

#include<bits/stdc++.h>
#define maxn 100010
#define inf 0x7f7f7f7f
#define ll long long
using namespace std;

int n,q;
struct node
{
ll d,c;
} a[maxn];
stack<ll> s;
ll f[maxn][25],u[maxn][25];

int main()
{
cin>>n>>q;
for(int i=1; i<=n; i++)
scanf("%lld%lld",&a[i].d,&a[i].c);

//单调栈处理出圆盘上的金币流2^0次后能到哪个圆盘
for(int i=n; i>=1; i--)
{
//出栈，直到栈顶的直径比i大
while(!s.empty()&&a[s.top()].d<=a[i].d) s.pop();
//所以s.top()就是能接住i金币的圆盘
if(!s.empty()) f[i][0]=s.top();
//入栈，始终保证栈中元素单调递增
s.push(i);
}
//倍增得到圆盘上的金币流2^n次后能到哪个圆盘
for(int i=1; i<=23; i++)
for(int j=1; j<=n; j++)
f[j][i]=f[f[j][i-1]][i-1];

//倍增得到圆盘上的金币流2^n次后会消耗掉的金币数量
for(int i=1; i<=n; i++)
if(f[i][0]==0) u[i][0]=inf; //初始化u数组
for(int i=1; i<=n; i++)
u[i][0]=a[f[i][0]].c;
for(int i=1; i<=23; i++)
for(int j=1; j<=n; j++)
u[j][i]=u[j][i-1]+u[f[j][i-1]][i-1];//倍增

//回答询问
while(q--)
{
ll x,v;
scanf("%lld%lld",&x,&v);
if(v<=a[x].c)
{
printf("%lld\n",x);
continue;
}
v-=a[x].c;
// 如果流2^i次后能被接住，则流到对应的圆盘上
for(int i=23; i>=0; i--)
if(u[x][i]<=v) v-=u[x][i],x=f[x][i];
// 如果还剩下金币，就会流到下面一个
if(v) x=f[x][0];
printf("%lld\n",x);
}
return 0;
}

D-拍照

#include<bits/stdc++.h>
using namespace std;
struct node
{
int x;
int id;
}a[70000];
int n;
int sum;//部门总数
int cnt[10010],now;//当前每个部门员工数，当前出现的部门数
bool id[10010];
bool cmp(node a,node b)
{
return a.x<b.x;
}
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i].x>>a[i].id;
if(!id[a[i].id])
{
sum++;
id[a[i].id]=1;//记录部门总数
}
}
sort(a+1,a+n+1,cmp);
int l=1, ans=0x7f7f7f7f;
for(int i=1; i<=n; i++) //双指针，枚举右边的指针
{
cnt[a[i].id]++;
if(cnt[a[i].id]==1) now++;
while(cnt[a[l].id]>1) //左指针尽量右移
{
cnt[a[l].id]--;
l++;
}
if(now==sum) ans=min(ans,a[i].x-a[l].x);
}
cout<<ans;
return 0;
}

E-读书

#include <bits/stdc++.h>
using namespace std;
const int mod=1000007;
int n,m,ans,minn=99999999;
char ch[11];
int a[1010],b[100010];
bool book[1100000];
int vis[1100000];
int ha(char a[])
{
int len=strlen(a),h=1;
for(int i=0; i<len; i++) h=(h+a[i])*131%mod;
return h;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",ch);
a[i]=ha(ch);
book[a[i]]=1;
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",ch);
b[i]=ha(ch);
if(book[b[i]]&&!vis[b[i]])
{
ans++;
vis[b[i]]=1;
}
}
if(ans==0)
{
printf("0\n0");
return 0;
}
memset(vis,0,sizeof vis);
int l=1,r=1,cnt=ans;
while(1)
{
if(!cnt)//如果已经找齐了所有的单词 尝试有没有更优的解
{
while(!book[b[l]]) l++;//如果l不是需要的单词，l向右移动
if(l==m+1) break;
minn=min(minn,r-l);
if(vis[b[l]]==1) cnt++,vis[b[l]]--,l++;//如果当前l只选了一次 cnt++ 尝试找更优解
if(vis[b[l]]>=1) vis[b[l]]--, l++;
}
else//如果没找齐，从左向右找，只移动右端点
{
if(r==m+1) break;
if(book[b[r]])
{
if(!vis[b[r]]) cnt--;
vis[b[r]]++;
}
r++;
}
}
printf("%d\n%d",ans,minn);
return 0;
}