D题的另类体验 wa过的人都知道除法精度不够,有没有什么办法将除法转乘法呢? 求逆元!!! 比赛时取模数写错导致一直没过........ from math import inf import sys mod = int(1e9+7) input = sys.stdin.readline def inv(a,b): return a*pow(b,mod-2,mod)%mod for _ in range(int(input())): n = int(input()) vis = {} x = [*map(lambda x:int(x), input().s...

牛客py啥要时候才能支持sortedcontainer

考虑一个性质A xor B xor B = A 先记录a数组前缀异或值 注意数据量为3e3 可以开一个vector保存一下所以区间异或值，对区间排序按异或值 最后先将查询值保存，排序，从最大查询值大开始将区间存入set，保存答案即可。 #include<bits/stdc++.h> #define rep(a,b) for( int i= a; i <= b ; ++i) #define rep2(a,b) for( int j=a; j <= b ; ++j) #define pre(a,b) for( int k= a; k >= b ; --k) #defi...

D 没啥好说的，考虑加法取模的性质 from math import gcd a = input() b = int(input()) r = 0 for i in a: r = r * 10 + int(i) r %= b print(gcd(r , b)) E 跑dijkstra #include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 505; int n; int mp[N][N], dis[N][N]; bool vis[N][N]; struct...

https://ac.nowcoder.com/acm/contest/73810/D 状压dp法 #include<bits/stdc++.h> using namespace std; int dp[15][1 << 14]; int arr[15][15]; int main(void) { for (int i = 1; i <= 13; i++) for (int j = 1; j <= 13; j++) cin >> arr[i][j]; for (int i = 1; i &...

思路看注释 #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 5; struct node { int x, y, z; }nod[N]; int n, h, k, arr[N], cnt, sum; int sm[N]; signed main(void) { cin >> n >> h >> k; for (int i = 1; i < N; i++)//打表，存一下在下标时间内可造成的伤...

https://ac.nowcoder.com/acm/problem/266841 n,m=map(int,input().split()) mp=[list(input()) for _ in range(n)] vis=[[False]*1005 for _ in range(1005)] l,r,u,b=m,0,0,n cnt=0 ans=0 def dfs (x,y): global l,r,u,b,cnt l=min(l,y) r=max(r,y) u=max(u,x) b=min(b,x) cnt+=1 vis[x][y]...

#include<bits/stdc++.h> #define lt i<<1 #define rt i<<1|1 using namespace std; const int N = 1e5 + 5; int n, w[N], m; struct segment_tree { int l, r, mn; }tr[N * 4]; int val, maxlen, minlen; struct node { int a, b; node() {} node(int a, int b) :a(a), b(b) {} bool operator<...

E 考察树的直径。 先随便取个点，搜出最距离此点最远节点，再以这个节点为起点，再搜一遍，最后重复一遍。搜的过程中记录一下距离是否大于2. #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 5; int n; bool vis[N]; struct node { int to, next; }edge[N]; int head[N], cnt; int ans; int mxlen; int nod; void add(int u, int v)//前向星记录边 { edge[++cnt...

H 高中物理 分两种情况，具体看代码。 ">using namespace std; double r, d, v, a, o; int main(void) { cin >> r >> d >> v >> a >> o; double h = r * cos(o); if (d <= h)//图1的情况 { double l = r * asin(d / r); double L = 0, R = 10000; for (int i = 1...

G 试了很多遍，字母表再加一个字就过了（^_^） ">using namespace std; int main(void) { cout<<"abcdefghijklmnopqrstuvwxyzp"; }

E 先看数据10^5 排除O(n^2)和O(n^3)，想一想如何遍历一遍得出答案？ 761只有3位数，我们先考虑中间的6。 用map先存一下6的下标，用前缀和记录7和1。 然后遍历一遍map，得出答案。 ">using namespace std; const int N = 1e5 + 10; int ans; string s; unordered_map<int, int>arr6; int sum1[N]; int sum7[N]; int main(void) { getline(cin, s); for (int i = 0; i < s.s...

#思路： 状态压缩 由Cn0+Cn1+Cn2+Cn3+....+Cnn=2^n。我们能确定要输出多少次。 用1表示选了哪个数，用0表示未选，可以发现选取排列可以2进制表示。 如：当n=2时； I. 00 表示都不选。 II. 01 表示选1。 III.10 表示选2. IV. 11 表示选1和2。 好了，我们现在已经知道如何表示了，接下来用递归来模拟： #include<bits/stdc++.h> using namespace std; int N; void dfs(int n) { if(n==(1<<N))return; int r...

思路： 数据范围为1—1e18.直接取模相乘肯定会爆。这里我们考虑一个性质：a*2*b/2=a*b; 我们知道a*2<1e20.所以我们可以对a倍增，b倍减。 话不多说，上算法： ll ans=0;         while(b)     {         if(b&1){ans=(ans+a)%p;}             a=(a*2)%p;...