Codeforces Round #632 (Div. 2) C. Eugene and an array (map&前缀和) 题目传送门  题意：求给定数组所有区间和非0的区间个数。 思路：   AC代码： #include<iostream> #include<map> using namespace std; typedef long long ll; map<ll,ll>mp; ll n,sum,mx,ans;//mx满足(前一个区间)[idx,i-1]==0和[idx,i]==0的最大idx  int main(){ mp[0]=1;//初...

Codeforces Round #632 (Div. 2) D. Challenges in school №41 (模拟&思维） 题目传送门 题意：给定序列求使得转身k轮刚好序列中不再存在转身的序列的解决方案。 思路：   AC代码： #include<bits/stdc++.h> using namespace std; vector<vector<int> >ans; int a[3050]; char c; int main(){ int n,k,sum=0; cin>>n>>k; for(int i=1;i<...

Codeforces Round #632 (Div. 2) F. Kate and imperfection（贪心&素数筛） 题目传送门 题意：求给定[1,n]的序列，长度为从2到n的序列中gcd(a,b)（a不等于b)的最大值。 思路：根据贪心思想，显然先将最大公约数为1的放入集合（即素数），再将最大公约数为2的放入集合（比如2），再将最大公约数为3的放入集合（比如6）依次类推，显然当放入一个合数时，它的所有因数都在集合中(它的因数都被筛过），因此此时的答案为它的最大因子。利用埃氏筛从小到大遍历不断更新最大因子即可。 AC代码： #include<bits/stdc++.h&...

P1033 自由落体 (数论） 题目传送门 题意：物理题0-n-1 n个位置的小球自由落体，一长l高k的小车从s1开始以速度v匀速运动，求小车最多接住多少个小球 思路：找到最早和最晚接到的小球编号，相减+1即可。注意本题卡精度算出i_l和i_r分别要减1e4 和加1e-4。还要i_l都到不了最左端的情况。 #include<bits/stdc++.h> using namespace std; int n; double h,s1,v,l,k; int main() { cin>>h>>s1>>v>>l>>k>&gt...

P1037 产生数 (高精&DFS) 题目传送门 给定以一大整数，k中数的转换方式。求一共可以转换为多少种不同的数。 思路：利用DFS求每一位可以转换的情况，根据乘法原理将每一位的情况相乘即为答案。 #include<bits/stdc++.h> using namespace std; int k,ans[100]={1},vis[10],tmp;//vis[i]标记该数是否被访问过  pair<int,int>p[20]; void dfs(int x){ //搜索每位可能的情况  for(int i=1;i<=k;i++) if(!vis[p[i]....

P1045 麦森数 （数论&高精） 题目传送门 题意：2 ^ p-1的位数并输出后500位数 思路：2 ^ p-1与2 ^ p的位数相同(因为2 ^ p个位数不为0），所以将2 ^ p转换为10 ^ n 形式即可  AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e3+5; int ans[N],tmp[N],a[N],p; void muti(int *x,int *y){ //高精x*y  memset(tmp,0,sizeof tmp); for(int i=1;i<=500;i++...

Educational Codeforces Round 85 C. Circle of Monsters(贪心） 思路：考虑每个怪物对答案的贡献，若前一个能炸死当前怪物则对答案无贡献，否则贡献为其差值，除此外我们还需选取一个最小的第一个子弹打死的怪物，通过分别在被炸死的怪物和没被炸死怪物中取最小值即可。 AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+5; ll a[N],b[N]; int main(){ int t; scanf("%d&...

Nowcoder Practice 61 D.最短路变短了 (最短路） 题目传送门 题意：给定有向带权图，求将一条边反向是否使最短路变短。 思路：显然修改后若不走这条边最短路不会变短，若走这条路需要比较d[v]+w+d1[u]与d[n]的关系 （d[ i ]表示到1的距离，d1[ i ]表示到n的距离。 SPFA 链式 #include<bits/stdc++.h> using namespace std; #define mst(a) memset(a,0,sizeof a)  typedef long long ll; const int N=1e5+5,M=2e5+5,inf...

Nowcoder Practice 61 C.四个选项 题目传送门 题意：给定12个选择题，限定每个选项个数，和若干个两两相等的选项。求方案数 思路：由于只有12个，可以使用DFS，对每个题一边搜索一边判重。 #include<bits/stdc++.h> using namespace std; int a[20][20],b[5],c[5],d[20],m,ans; void dfs(int id){ if(id>12){ ans++; return; } for(int i=1;i<=4;i++) if(c[i]<b[i]){ //当前颜色个数小于目标颜色个...

学习笔记：哈希字符串 第一种方法：自然溢出法。  实例代码：这里prime=233 #include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; ull h[15],p[15]; char s[15]; int main(){ scanf("%s",s+1); int len=strlen(s+1); p[0]=1; for(int i=1;i<=len;i++) p[i]=p[i-1]*233,h[i]=h[i-1]*233+s[i]; for(int i=1;i...

Nowcoder Practice 61 E.相似的子串（Hash&二分) 题意：求给定字符串中相同但不相交的子串最大个数。 思路：二分查找子串长度，然后对每个长度从右端开始递推结果。 #include<bits/stdc++.h> using namespace std; const int N=2e5+5,mod=1e9+7; typedef unsigned long long ull; ull h[N],p[N]={1}; char s[N]; int n,k,ans; bool fun(int len){ map<ull,pair<int,int&gt...

「StOI-1」IOI 排名 （贪心） 题意：m个人参加n场比赛，给定一个人n次比赛排名，求给人总排名最好和最差是多少（分数无上限，下限为1） 思路：  #include<bits/stdc++.h> using namespace std; int main(){ int t; cin>>t; while(t--){ int n,m,a=0,b=0; cin>>n>>m; for(int i=1,x;i<=n;i++) cin>>x,a+=m-x,b+=x-1;//贪心  a=min(a,m-1),b=min(b,m-1); ...

P1056 排座椅 （贪心&排序) 题目传送门 思路：分别求出分割每行每列的同学对数，然后排序，分别取k和l个即可。 #include<bits/stdc++.h> using namespace std; const int N=1e3+5; struct p{ int id,v; }a[N],b[N]; bool cmp(p a,p b){ return a.v>b.v; } int vis[N][2]; int main(){ int n,m,k,l,d; cin>>n>>m>>k>>l>>d; for...

P1057 传球游戏 （DP） 题目传送门 题意：n个人传球，求从1开始传，传m次传给1的方案数。 思路：  AC代码： sol1：取模的方法： #include<cstdio> int a[35][35]; int main(){ int n,m; scanf("%d%d",&n,&m); a[0][0]=1; for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i+1][(j-1+n)%n]+=a[i][j],a[i+1][(j+1)%n]+=a[i][j]; printf("%d\n...