【题解】牛客NOIP暑期七天营-普及组3
A、X操作
20分做法：
状态压缩一下，枚举0~((1<<m)-1)，统计1的个数表示x加的操作次数，减的操作次数就是m-x，判断是否x==y即可
50分做法：
直接跑m次操作，如果发现x<y则x++,x>y则x--,x==y可以任意操作，这样贪心下去操作完后判断是否x==y即可80分做法：
在100分的基础上不开long long就只有80分了100分做法：
首先，判断的第一条件是m>=abs(x-y)，表示操作次数大于两数的差，因为如果操作次数小于两数的差了，那么x一定时无法变成y的，其次，如果操作abs(x-y)次后使x变成了y，这时如果操作次数是奇数，那么就无法达成，是偶数，我们可以通过反复加减的方式来使得x==y。
代码：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41171489B、填数
10分做法：
把所有位置爆搜一下，填1~4直接的任意数，搜索时判断某个终止状态的和是否<=m。
100分做法：
首先，对于没有限制的，显然我们填1即可，对于限制1，贪心的使得a[i]==a[i-1]，对于限制2，贪心的使得a[i]==a[i-1]+1，这样贪心下去，然后判断最终得到的总和是否小于等于m即可。C、区间中最多的数
10分做法：
暴力枚举
50分做法：
在100分做法的基础上，用数据结构去维护1~100每个数出现的次数，咋们就可以TLE了,时间复杂度O(100*q*log2(n)+100*n*log2(n))。
100分做法：
1<=a[i]<=100，用前缀和维护1~100每个数出现的次数，就可以O(1)的查询某个数在区间里出现的次数了，然后对于一次查询，只需要O(100)的暴力去统计即可，时间复杂度O(100*q+100*n)
代码：
D、子段和
50分做法：
对于每个查询操作，枚举所有区间，计算所有区间的和，判断区间的和是否等于x。
70分做法：
在50分做法基础上，进行剪枝，如果区间和大于等于x了，就没必要枚举后面的区间，如果查询的y大于总和了，就可以直接输出“No”。100分做法：
1.f[i][j]表示[i,j]这段区间的和，开一个vis数组保存每个和出现的次数，如果之星操作1，我们只需要删除n个区间的值，执行操作2，只需要假如n个区间的值，时间复杂度O(nm)。2.记录前缀和和一个vis数组，vis数组里保存某个前缀和出现的次数，对于每次查询O(n)的去跑所有前缀和，判断sum-x这个前缀和是否存在即可,时间复杂度最坏O(nm)。
3.由于数据水，时间复杂度O(n^2 m)的算法也被放过了，很遗憾我的数据这么水。
代码：
投递中国航天科工集团等公司7个岗位 >
