样例解释:
二元组如下:
- (1,1)(1,2)(1,3)(1,6)
- (2,1)(2,2)(2,3)(2,6)
- (4,1)(4,2)(4,3)(4,6)
共 12 组.
无序二元组如下:
- (1,1)(1,2)(1,3)(1,6)
- (2,2)(2,3)(2,6)
- (4,1)(4,2)(4,3)(4,6)
共 11 组
直接筛素数
- #include <bits/stdc++.h>
- using namespace std;
- int a[10005];
- void init(){
- for (int i = 1; i <= 10000; ++i){
- for (int j = i; j <= 10000; j += i){
- a[j]++;
- }
- }
- }
- int main(){
- int t;
- init();
- cin>>t;
- int x,y;
- while(t--){
- cin>>x>>y;
- int one = a[x];
- int two = a[y];
- int ans = __gcd(x,y);
- ans = a[ans];
- cout<<one*two-((ans-1)*ans)/2<<endl;
- }
- return 0;
- }
链接: https://www.nowcoder.com/acm/contest/185/B
路径数量
时间限制: C/C++ 1 秒, 其他语言 2 秒
空间限制: C/C++ 131072K, 其他语言 262144K
64bit IO Format: %lld
题目描述
给出一个 n * n 的邻接矩阵 A.
A 是一个 01 矩阵 .
A[i][j]=1 表示 i 号点和 j 号点之间有长度为 1 的边直接相连.
求出从 1 号点 到 n 号点长度为 k 的路径的数目.
输入描述:
第 1 行两个数 n,k (20 n 30,1 k 10)
第 2 行至第 n+1 行, 为一个邻接矩阵
输出描述:
题目中所求的数目
示例 1
输入
复制
- 4 2
- 0 1 1 0
- 1 0 0 1
- 1 0 0 1
- 0 1 1 0
输出
复制
2
说明
样例如图:
第一条路径: 1-2-4
第二条路径: 1-3-4
矩阵乘法可以解决此问题.
- #include <bits/stdc++.h>
- #define pb push_back
- #define test(a) cout<<a<<endl
- #define ll long long int
- using namespace std;
- ll n,k,x;
- ll cnt = 0;
- ll v[32][32],b[32][32];
- ll vis[32][32];
- int main(){
- cin>>n>>k;
- for (int i = 1; i <= n; ++i){
- for (int j = 1; j <= n; ++j){
- cin>>v[i][j];
- vis[i][j] = v[i][j];
- }
- }
- k--;
- while(k--){
- memset(b,0,sizeof(b));
- for(int i = 1; i <= n; ++i){
- for(int j = 1; j <= n; ++j){
- for(int p = 1; p <= n; ++p){
- b[i][j] += v[i][p]*vis[p][j];
- }
- }
- }
- for (int i = 1; i <= n; ++i){
- for (int j = 1; j <= n; ++j){
- v[i][j] = b[i][j];
- }
- }
- }
- cout<<v[1][n]<<endl;
- return 0;
- }
链接: https://www.nowcoder.com/acm/contest/185/C
数列下标
时间限制: C/C++ 1 秒, 其他语言 2 秒
空间限制: C/C++ 131072K, 其他语言 262144K
64bit IO Format: %lld
题目描述
给出一个数列 A, 求出一个数列 B.
其中 Bi 表示 数列 A 中 Ai 右边第一个比 Ai 大的数的下标(从 1 开始计数), 没有找到这一个下标 Bi 就为 0
输出数列 B
输入描述:
第一行 1 个数字 n (n 10000)
第二行 n 个数字第 i 个数字为 Ai (0 Ai 1000000000)
输出描述:
一共一行, 第 i 个数和第 i+1 个数中间用空格隔开.
示例 1
输入
复制
6 3 2 6 1 1 2
输出
复制
3 3 0 6 6 0
说明
样例不用解释
这题就用栈来模拟一下了.
- #include <bits/stdc++.h>
- #define test(a) cout<<a<<endl
- using namespace std;
- struct Node{
- int to,val;
- };
- stack<Node> sk;
- int an[10005];
- int n,x;
- int main(){
- cin>>n;
- for (int i = 1; i <= n; ++i){
- cin>>x;
- if(sk.empty()){
- sk.push(Node{i,x});
- }else{
- if(sk.top().val>= x){
- sk.push(Node{i,x});
- }else{
- while(!sk.empty() && sk.top().val <x){
- an[sk.top().to] = i;
- sk.pop();
- }
- sk.push(Node{i,x});
- }
- }
- }
- for(int i = 1; i <= n; ++i){
- cout<<an[i]<<" ";
- }
- cout<<endl;
- return 0;
- }
链接: https://www.nowcoder.com/acm/contest/185/D
- #include <bits/stdc++.h>
- #define test(a) cout<<a<<endl
- #define ll long long int
- using namespace std;
- ll n,x;
- int main(){
- cin>>n;
- int ans = (int)sqrt(n);
- cout<<ans<<endl;
- return 0;
- }
- #include <bits/stdc++.h>
- using namespace std;
- string s;
- int n;
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0),cout.tie(0);
- cin>>n;
- cin>>s;
- int l = 0;
- int ans = 0;
- for(int i = 0; i <s.length(); i++){
- if(s[i]=='(')
- l++;
- else{
- if(l==0)
- ans++;
- else
- l--;
- }
- }
- int cnt = ans%2==0?ans/2:ans/2+1;
- cout<<cnt<<endl;
- return 0;
- }
- #include <bits/stdc++.h>
- #define ll long long int
- #define pi acos(-1)
- #define eps 1e-10
- #define e 2.718281828459
- using namespace std;
- int main(){
- ll t;
- cin>>t;
- double ans = t*log10(t);
- ll l = 1,r = 1e15;
- while(r - l> 1){
- ll mid = (l + r)>>1;
- double cnt = log10(sqrt(2.0 * mid * pi)) + mid * log10(mid / e);
- if(cnt - ans> eps){
- r = mid;
- }else{
- l = mid;
- }
- }
- cout<<r<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2759688.html