题意： 思维题。输入n，现有m位的数组array（m<n），从[ 1，n-m ]中随机生成x，将[ 1，2，3…x ]排列到array后面组成新数组，直到数组有n位。求对于特定的n有几种不同的数组
思路：
①模拟一下结果就是2n-1 .
②这题要用快速幂 ，不然会超时
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b%2==1)
{
res*=a;
res%=mod;
}
b/=2;
a*=a;
a%=mod;
}
return res;
}
int main()
{
ll n,t;
cin>>t;
while(t--)
{
cin>>n;
ll x;
x=qpow(2,n-1)%mod;
cout<<x<<endl;
}
return 0;
}
题意： T组数据，每组输入宝藏坐标（x，y），每次从（0,0）出发，第t秒内可以走t个单位，输出到达目标的最短时间和每秒结束后的实时坐标。注意：第t秒内必须精准地走完t个单位，不多不少。
思路： 模拟题。
代码实现大概分这些步骤：
①初始化、处理坐标、特判
②构造函数：先走横坐标
③构造函数：再走纵坐标
④构造函数：处理剩余步数
⑤判断奇偶后处理或转化
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1e5+5;
int t,walk,dis;
//t为时间 walk为该秒可走步数 dis为剩余步数
ll xi[maxn],yi[maxn],x,y,fx,fy,xx,yy;
//xi数组和yi数组为实时位置 fx和fy是坐标的正负性
void remanent() //处理剩余步数
{ //如果剩余步数与相差步数同奇偶 可一秒走完
//否则总是走到距离目标值的一步之距--->转化成同奇偶的情况
if((y-yy)%2==1)
{
if(dis%2==1)
{
t++;
xi[t]=xx*fx;
yi[t]=y*fy;
}
else
{
t++;
xi[t]=xx*fx;
yi[t]=(y-1)*fy;
t++;
xi[t]=xx*fx;
yi[t]=y*fy;
}
}
else
{//dis为奇数可以实现走到一步之距
//为偶数可以实现待在原地
if(dis%2==0)
{
t++;
xi[t]=xx*fx;
yi[t]=y*fy;
}
else
{
t++;
xi[t]=xx*fx;
yi[t]=(y+1)*fy;
t++;
xi[t]=xx*fx;
yi[t]=(y+1)*fy;
t++;
xi[t]=xx*fx;
yi[t]=y*fy;
}
}
}
void walky() //再走纵坐标
{
if(dis>=y) //剩余步数>纵坐标
{
remanent(); //处理剩余步数
return;
}
yy+=dis;
t++;
xi[t]=xx*fx;
yi[t]=yy*fy;
walk++;
while(1)
{
yy+=walk;
if(yy>=y)
{ //纵坐标超过目标值 撤回上一秒的操作
dis=walk; //撤回后剩余步数为walk
yy-=walk; //撤回后纵坐标
remanent(); //通过绕远路来耗完剩余步数
return;
}
walk++; //更新一系列变量
t++;
xi[t]=xx*fx;
yi[t]=yy*fy;
}
}
void walkx() //先走横坐标
{
while(1)
{
xx+=walk;
if(xx>=x) //走完横坐标
{
dis=xx-x; //这一秒内剩余可走步数
xx=x;
walky(); //再走纵坐标
return;
}
//更新横纵坐标和时间、步数
walk++;
t++;
xi[t]=xx*fx;
yi[t]=yy*fy;
}
}
int main()
{
int T;
scanf("%d",&T);
for(int tt=1;tt<=T;tt++)
{
scanf("%lld%lld",&x,&y);
printf("Case #%d:\n",tt);
xx=0,yy=0,t=0,dis=0,walk=1;
fx=1,fy=1; //考虑正负号
if(x<0) fx=-1;
if(y<0) fy=-1;
x=abs(x);
y=abs(y);
if(x==0&&y==0) printf("0\n"); //(0,0)特判
else
{
walkx(); //先走横坐标
printf("%d\n",t);
for(int i=1;i<=t;i++)
printf("%lld %lld\n",xi[i],yi[i]);
}
}
return 0;
}
题意： 存图，找最多有几个有形如上图的“鸡爪”图形，要求每个鸡爪要是不同边集的。
思路： ①先要搞清楚题意，“鸡爪”图形是上面一整个，不是一部分 ②找准合适的节点有规律地分析
观察可知，鸡腿 需要除父节点外的两条边/点 ，爪子 需要除父节点外的三条边/点 。
∴只需对两部分排列组合后相乘 即可。示例中鸡腿部分为sum=C（deg[2]-1，2），爪子部分为res=C（deg[4]，3）
同理，用dfs从根节点开始不断遍历邻居即可。要注意一些特判情况。考虑到数据范围，组合数需要用快速幂再取模。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e5+5;
const ll mod = 998244353;
int n;
ll ans,deg[maxn],s[maxn];;
int cnt, head[maxn];
struct edge
{
int v, next;
}e[maxn*2];
void add (int u,int v) //存边
{
e[++cnt] = {v, head[u]}; head[u] = cnt;
e[++cnt] = {u, head[v]}; head[v] = cnt;
}
void init() //s数组存n的阶乘n!
{
s[0] = 1;
s[1] = 1;
for(ll i = 2; i <= 500000; i++)
s[i] = s[i - 1] * i % mod;
}
ll qpow(ll n,ll k) //快速幂
{
ll ans=1;
while(k)
{
if(k&1)
ans=ans*n%mod;
n=n*n%mod;
k/=2;
}
return ans;
}
ll C(ll n,ll m) //组合数
{
if(n<m) return 0;
return s[n]*qpow(s[n-m]*s[m]%mod,mod-2)%mod;
}
void dfs1(int u,int fa)
{ //从根节点开始遍历相邻的点 记录每个节点入度
deg[u]=0;
for (int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if (v==fa) continue;
dfs1(v, u);
deg[u]++;
}
}
void dfs2(int u,int fa)
{
ll res=0,sum;
//res sum分别负责统计爪子和鸡腿上的情况
if(fa!=0) sum=deg[u]+1;
else sum=deg[u];
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)
{
if(fa==1&°[fa]>=4)
res=(res+C(deg[fa]-1,3))%mod;
if(fa!=1&°[fa]>=3)
res=(res+C(deg[fa],3))%mod;
}
else
{
dfs2(v,u);
if(deg[v]>=3)
res=(res+C(deg[v],3))%mod;
}
}
ans=(ans+res*C(sum-1,2))%mod;
}
int main()
{
scanf("%d",&n);
init();
memset(deg,0,sizeof(deg));
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
}
dfs1(1,0);
dfs2(1,0);
printf("%lld",ans);
return 0;
}
题意： 输入k，给出2k 个数，操作：每次平分两段，可舍弃任一部分，直到留下的序列为非降序则结束，求最少需要几次操作
思路： 每次截取2k 的区间，依次遍历查询每个区间，查完再二分重复从头遍历，直到有找到非降序列结束。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+1e5;
int k,a[maxn];
int main()
{
scanf("%d",&k);
int n=1<<k;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int l=1,r=n,num=0,len=n;
for(int i=l;i<r;i++)
{
if(a[i]<=a[i+1]) continue; //符合条件 能顺利跳出for循环说明是非降序列
else //下一组or继续二分
{
if(l+len>n) //已是当前最后一组 继续二分
{
len/=2;
num++;
l=1;
r=l+len-1;
i=l-1;
if(len==1) break;
}
else //跳至下一组区间
{
l+=len;
r+=len;
i=l-1;
}
}
}
printf("%d",num);
return 0;
}
也可以用线段树 做（显然我写不出），这里贴一篇很好的科普博客—>传送门
码还是参照铁子哥的（代码作者：Sstee1XD）
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1e5;
int ans = 1;
int a[N], k, n;
struct Seg
{
int minn[N << 2], maxx[N << 2];
bool flag[N << 2];
void up(int id, int l, int r) //向上更新线段树
{
if (flag[id << 1 | 1] && flag[id << 1] && maxx[id << 1] <= minn[id << 1 | 1])
{ //即id*2+1
flag[id] = true;
minn[id] = minn[id << 1];
maxx[id] = maxx[id << 1 | 1];
ans = max(r - l + 1, ans);
}
}
void build(int id, int l, int r) //建树
{
flag[id] = false;
minn[id] = 0;
maxx[id] = 0;
if (l == r)
{
flag[id] = true;
maxx[id] = a[l];
minn[id] = a[l];
return;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
up(id, l, r);
}
}seg;
void solve()
{
scanf("%d", &k);
int n = 1 << k; //即k=2^k
for (int i = 1; i<= n; ++i) scanf("%d", &a[i]);
seg.build(1, 1, n);
printf("%d\n", k - __lg(ans));
}
int main() {
int t = 1;
while(t--) solve();
return 0;
}
题意： 输入n m k，n个数，每m个数一组，进行清除操作，统计每组操作结束后有几个数为0，最后累加。注意 ，每次操作结束后，原数组的数据不会改变。
思路： 求每组有几个从k开始的连续的不同的数，再求每个不同的数的个数，最后累加。直接用for循环会超时，要建两棵线段树降低时间复杂度。
①第一棵线段树统计当前区间的[k,k+m]有几个连续不同的数，统计出该区间需要减去的数sum
②第二棵线段树统计各个不同的数的个数，再依次累加
③遍历每棵线段树
没想到吧 根本不会写 哈哈:)
或者用树状数组 （码是铁子哥的，菜鸡还没完全看明白呜呜，来个大佬写个注释吧呜呜）（代码作者：Sstee1XD）
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
typedef long long ll;
int n, q, m, k, idk;
int a[N], b[N], id[N];
ll tot[N], had[N];
int num[N];
int lowbit(int x) {
return x & -x;
}
void add(int i, ll v, ll bit[]) {
while (i <= q) {
bit[i] += v;
i += lowbit(i);
}
}
ll query(int i, ll bit[]) {
ll res = 0;
while (i > 0) {
res += bit[i];
i -= lowbit(i);
}
return res;
}
void ins(int i) {
if (!num[i]) {
add(i, 1ll, had);
}
add(i, 1ll, tot);
num[i]++;
}
void del(int i) {
num[i]--;
add(i, -1ll, tot);
if (!num[i]) {
add(i, -1ll, had);
}
}
ll gao(int u, int v) {
if (!num[idk]) return 0;
ll res = 0;
int l = idk + 1, r = q, mid;
while (l <= r) {
mid = l + r >> 1;
ll tmp = query(mid, had) - query(idk - 1, had);
if (tmp < mid - idk + 1) r = mid - 1;
else l = mid + 1;
}
int len = b[l - 1] - b[idk] + 1;
int pos = lower_bound(b + 1, b + 1 + q, len) - b;
if (pos > q || b[pos] > len) pos--;
if (pos <= 0) return 0;
len = pos;
return query(len, tot);
}
void solve() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + 1 + n);
q = unique(b + 1, b + 1 + n) - b - 1; //去重函数
//q为去重后尾元素下标 即有几个不同的数
int Q = q;
for (int i = 2; i <= q; ++i) {
if (b[i] - b[i - 1] > 1) {
b[++Q] = b[i] - 1;
}
}
q = Q;
sort(b + 1, b + 1 + q);
for (int i = 1; i <= n; ++i) {
id[i] = lower_bound(b + 1, b + 1 + q, a[i]) - b;
if (a[i] == k) idk = id[i];
}
if (!idk) {
puts("0");
return;
}
ll ans = 0;
for (int i = 1; i <= m; ++i) {
ins(id[i]);
}
for (int i = 1; i + m - 1 <= n; ++i) {
if (i != 1) {
del(id[i - 1]);
ins(id[i + m - 1]);
}
ans += gao(i, i + m - 1);
}
printf("%lld\n", ans);
}
int main() {
int t = 1;
while(t--) solve();
return 0;
}
这次省赛选拔赛签到题都没做完要反省。
一个是因为几个人都没有去准备，直接裸考，自己准备的纸质材料也没有，只有几本没看过的算法书。
还有一个是因为确实实力也还没有，其实J挺水，如果静下来好好去想，在赛场上应该还是能写出的，当时几个人状态都不积极觉得会是比较复杂的二分题，还因为觉得写循环必超时就根本没去写 （这边建议要是怕超时以后用个clock（）函数—>传送门）
希望自己可以这两个月坚持多多刷题，争取六月份个人选拔赛可以留下来呆在实验室。
还要继续加油呐。
Microsoft VBScript 编译器错误 错误 '' 缺少语句 ActiveServerPages,ASP0126(0x...
文章目录 一、文件的基础知识 1.什么是文件 2.文件名 3.文件类型 4.文件指针 二...
前言 众所周知，MySQL广泛应用于互联网的OLTP（联机事务处理过程）业务系统中，...
今天分享一下以前入职现在公司第一次发布项目遇到的一个问题，一个数据库读写分...
select name="XlSheet" % vOptions = " option /option " Do While Not oSchemaR...
本文介绍了SpringBoot集成jsp（附源码）+遇到的坑 ，分享给大家 1、大体步骤 （1...
在***DAOImpl.java中的代码如下 复制代码 代码如下: public String getCompuName...
比较吃力的地方是drop到播放列表，查MSDN查了n久，还有WindowMediaPlayer6.x插件...
北京邮电大学 张剑 XML的局限性 目前，许多Web网站的内容数据都存放在数据库或数...
1编写一个Java程序片断以定义一个表示学生的类Student。这个类的属性有“学号”...
