正文

"字节跳动杯"2018中国大学生程序设计竞赛-女生专场solution(代码片段)

dup4  dup4  2023-01-11  148

关键词：

A - 口算训练

题意：询问 $[L, R]$区间内的所有数的乘积是否是D的倍数

思路：考虑分解质因数

显然，一个数$x > sqrtx 的质因子只有一个$

那么我们考虑将小于$sqrt x$ 的质因子用线段树维护

其他质因子用vector 维护存在性

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define N 100010
  5 #define block 317 
  6 vector <int> fac[N], bigfac[10010];
  7 int t, n, q;
  8 int arr[N], pos[N], cnt; 
  9 
 10 void init()
 11 
 12     cnt = 0;
 13     memset(pos, 0, sizeof pos);
 14     for (int i = 2; i < N; ++i)
 15     
 16         if (pos[i] || i > block) continue;
 17         for (int j = i * i; j < N; j += i)
 18             pos[j] = 1; 
 19     
 20     for (int i = 2; i < N; ++i) if (!pos[i]) pos[i] = ++cnt;
 21     for (int i = 2; i <= 100000; ++i)
 22     
 23         int n = i;
 24         for (int j = 2; j * j <= n; ++j)
 25         
 26             while (n % j == 0)
 27             
 28                 n = n / j;
 29                 fac[i].push_back(j);  
 30             
 31         
 32         if (n != 1) fac[i].push_back(n);
 33         sort(fac[i].begin(), fac[i].end());
 34     
 35 
 36 
 37 int T[80]; 
 38 struct SEG
 39 
 40     #define M N * 300
 41     int a[M], lson[M], rson[M], cnt;
 42        void init()  cnt = 0; 
 43     void pushup(int id)  a[id] = a[lson[id]] + a[rson[id]]; 
 44     void update(int &id, int l, int r, int pos)
 45      
 46         if (!id) 
 47         
 48             id = ++cnt;
 49             a[id] = lson[id] = rson[id] = 0;
 50         
 51         if (l == r) 
 52         
 53             ++a[id]; 
 54             return;
 55         
 56         int mid = (l + r) >> 1;
 57         if (pos <= mid) update(lson[id], l, mid, pos);
 58         else update(rson[id], mid + 1, r, pos);
 59         pushup(id);
 60     
 61     int query(int id, int l, int r, int ql, int qr)
 62     
 63         if (!id) return 0;
 64         if (l >= ql && r <= qr) return a[id];
 65         int mid = (l + r) >> 1;
 66         int res = 0;
 67         if (ql <= mid) res += query(lson[id], l, mid, ql, qr);
 68         if (qr > mid) res += query(rson[id], mid + 1, r, ql, qr);
 69         return res;
 70     
 71 seg;
 72 
 73 bool Get(int base, int need, int l, int r)
 74 
 75 //    printf("%d %d %d %d
", base, need, l, r);
 76     int have = 0;
 77     if (base < block)
 78     
 79         have = seg.query(T[pos[base]], 1, n, l, r);
 80         if (have < need) return false;
 81     
 82     else
 83     
 84         have = upper_bound(bigfac[pos[base]].begin(), bigfac[pos[base]].end(), r) - lower_bound(bigfac[pos[base]].begin(), bigfac[pos[base]].end(), l);
 85         if (have < need) return false;
 86     
 87     return true; 
 88 
 89 
 90 bool work(int l, int r, int d)
 91 
 92     if (d == 1) return true; 
 93     int base = fac[d][0], need = 1, have = 0;
 94     for (int i = 1, len = fac[d].size(); i < len; ++i)
 95     
 96         if (fac[d][i] != base) 
 97         
 98             if (Get(base, need, l, r) == false) return false;
 99             base = fac[d][i];
100             need = 1;  
101         
102         else ++need;
103     
104     return Get(base, need, l, r);
105 
106 
107 int main()
108 
109     init();
110     scanf("%d", &t);
111     while (t--)
112     
113         scanf("%d%d", &n, &q);
114         for (int i = 1; i < 10010; ++i) bigfac[i].clear(); 
115         for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
116         seg.init(); memset(T, 0, sizeof T); 
117         for (int i = 1; i <= n; ++i)
118         
119             for (auto it : fac[arr[i]])
120             
121                 if (it < block)
122                     seg.update(T[pos[it]], 1, n, i);                                    
123                 else
124                     bigfac[pos[it]].push_back(i);
125             
126             
127         for (int i = 1; i <= cnt; ++i) sort(bigfac[i].begin(), bigfac[i].end());
128         for (int i = 1, l, r, d; i <= q; ++i)
129         
130             scanf("%d%d%d", &l, &r, &d);
131             puts(work(l, r, d) ? "Yes" : "No");
132         
133     
134     return 0;
135

View Code

B - 缺失的数据范围

题意：给出$a, b, k$ 求一个最大的n 使得 $n^a cdot log ^b n <= k$

思路：二分但是要注意用高精度，求log的时候平方逼近

 1 import java.io.BufferedInputStream;
 2 import java.util.Scanner;
 3 import java.math.*;
 4 
 5 public class Main 
 6 
 7     public static BigInteger Get(BigInteger x, int a, int b)
 8     
 9         BigInteger two = BigInteger.valueOf(2);
10         BigInteger tmp = BigInteger.ONE;
11         BigInteger cnt = BigInteger.ZERO;
12         while (tmp.compareTo(x) < 0)
13         
14             tmp = tmp.multiply(two);
15             cnt = cnt.add(BigInteger.ONE);
16         
17         BigInteger res = x.pow(a).multiply(cnt.pow(b));
18         return res;
19     
20 
21 
22     public static void main(String[] args) 
23         Scanner in = new Scanner(new BufferedInputStream(System.in));
24         int t = in.nextInt();
25         int a, b; BigInteger k, l, r, mid, ans, zero, two, one;
26         zero = BigInteger.ZERO;
27         two = BigInteger.valueOf(2);
28         one = BigInteger.valueOf(1);
29         while (t-- != 0)
30         
31             a = in.nextInt();
32             b = in.nextInt();
33             k = in.nextBigInteger();
34             l = one;
35             r = k;
36             ans = zero;
37             while (r.subtract(l).compareTo(zero) >= 0)
38             
39                 mid = l.add(r).divide(two);
40                 if (Get(mid, a, b).compareTo(k) <= 0)
41                 
42                     ans = mid;
43                     l = mid.add(one);
44                 
45                 else
46                     r = mid.subtract(one);
47             
48             System.out.println(ans);
49         
50         in.close();
51     
52

View Code

C - 寻宝游戏

留坑。

D - 奢侈的旅行
留坑。

E - 对称数

留坑。

F - 赛题分析

水。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 #define INF 0x3f3f3f3f
 6 int t, n, m;
 7 int arr[N], brr[N];
 8 
 9 int main()
10 
11     scanf("%d", &t);
12     for (int kase = 1; kase <= t; ++kase)
13     
14         printf("Problem %d:
", kase + 1000);
15         scanf("%d%d", &n, &m);
16         for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
17         if (n == 0) puts("Shortest judge solution: N/A bytes.");
18         else printf("Shortest judge solution: %d bytes.
", *min_element(arr + 1, arr + 1 + n));
19         for (int i = 1; i <= m; ++i) scanf("%d", brr + i);
20         if (m == 0) puts("Shortest team solution: N/A bytes.");
21         else printf("Shortest team solution: %d bytes.
", *min_element(brr + 1, brr + 1 + m));
22     
23     return 0;
24

View Code

G - quailty算法

留坑。

H - SA-IS后缀数组

题意：求每对相邻的后缀字符的字典序大小

思路：从后面往前推，只考虑最高位，如果最高位相同，那么问题转化为一个子问题

比如 cm 和 acm 考虑最高位如果最高位相同问题转化为 m 和 cm 的大小关系

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1000010
 5 int t, n;
 6 char s[N];
 7 int ans[N];
 8 
 9 int main()
10 
11     scanf("%d", &t);
12     while (t--)
13     
14         int n;
15         scanf("%d%s", &n, s);
16         int len = strlen(s);
17         if (s[len - 1] != s[len - 2]) ans[len - 2] = s[len - 2] > s[len - 1];
18         else ans[len - 2] = 1;
19         for (int i = len - 3; i >= 0; --i)
20         
21             if (s[i] != s[i + 1]) ans[i] = s[i] > s[i + 1];
22             else ans[i] = ans[i + 1];
23         
24         for (int i = 0; i < len - 1; ++i) printf("%c", ans[i] ? ‘>‘ : ‘<‘);
25         puts("");
26     
27     return 0;
28

View Code

I - 回文树

留坑。

J - 代码派对

留坑。

K - CCPC直播

按题意模拟即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int t; 
 5 char s[20], sta[20];
 6 int Rank, x, pro;
 7 
 8 int main()
 9 
10     scanf("%d", &t);
11     while (t--)
12     
13         scanf("%d%s%d%s", &Rank, s, &pro, sta);
14         printf("%3d|%-16s|%d|[", Rank, s, pro);        
15         if (strcmp(sta, "Running") == 0) 
16         
17             scanf("%d", &x);
18             for (int i = 0; i < x; ++i) putchar(‘X‘);
19             for (int i = x; i < 10; ++i) putchar(‘ ‘);
20             printf("]
");
21         
22         else
23         
24             if (strcmp(sta, "FB") == 0) strcpy(sta, "AC*");
25             printf("    ");
26             printf("%-6s]
", sta);
27         
28     
29     return 0;
30

View Code

图解记一次手撕算法面试：字节跳动的面试官把我四连击了(代码片段)

字节跳动这家公司，应该是所有秋招的公司中，对算法最重视的一个了，每次面试基本都会让你手撕算法，今天这篇文章就记录下当时被问到的几个算法题，并且每个算法题我都详细着给出了最优解，下面再现当时的面试场景。... 查看详情

热搜第一！刚刚，快手宣布取消"大小周"加班！股价惨遭腰斩！字节跳动却吵翻了：不赚钱我来干嘛？少挣了10万！...

点击上方公众号「关注」和「星标」回复“1024”获取独家整理的学习资料！互联网大厂不卷了，刚刚，快手宣布7月将取消大小周。快手宣布7月起将取消大小周据36氪获悉，快手刚刚宣布从7月1日起取消大小周࿰... 查看详情

2018年ti杯大学生电子设计竞赛

2018年TI杯大学生电子设计竞赛目录标题2018年TI杯大学生电子设计竞赛1、A题：电流信号检测装置（本科）--2018年TI杯大学生电子设计竞赛2、B题：灭火飞行器（本科）--2018年TI杯大学生电子设计竞赛3、C题ÿ... 查看详情

锤子科技"临死前"被"接盘"，内部人士爆料已改签今日头条母公司

...的临时通知，要求改签劳动合同至今日头条的母公司——字节跳动。至于这是锤子科技真正再度复活还是借尸还魂都不重要，重要的是，作为忠实的锤粉者们，悬着的心终于要落地了。image早有征兆而根据早先新闻，就有相关媒... 查看详情

当字节跳动在美国输出中国式996...

作者 | GeorgiaWells/YoreeKoh/SalvadorRodriguez、来源 | WSJ 在荣克离职时发布的一份内部备忘录中，他说，“TikTok对待员工的方式与TikTok平台代表的东西截然相反。”TikTok上似乎有无穷无尽的消遣打趣、尽情舞动以及善意的恶... 查看详情

“华为杯”大连理工大学第12届大学生程序设计大赛

E膜法项链J更强的未来道具FG-C193K取模运算E膜法项链#include<cstdio>#include<algorithm>usingnamespacestd;#defineNmax1000010intA[Nmax*2];intN,W;longlongcnt[Nmax*2];voidadin(intx,intlx,intrx,inta)intl,r;l=x-lx;r=max(rx-max(x,N+1),0);cnt[rx-r-x+1]+=a;cnt[rx-r-x+1+r]-=a;cnt[r... 查看详情

2018年“三盟科技杯”中国大学生程序设计竞赛（湖南）

2018年“三盟科技杯”中国大学生程序设计竞赛（湖南）A.Easyh-index题目描述：给出一个数组$a_i$，求最大的$h$，使得至少有$h$个数不少于$h$。solution模拟。时间复杂度：$O(nlogn)$B.Higherh-index题目描述：写论文，当一份论文花... 查看详情

字节/字符——输入/输出流(代码片段)

...机如何存储中文的?当前平台默认编码集:GBK一个中文两个字节第一个字节:一定是负数第二个字节:一般是负数,可能也会是正数,不会影响的结果.*/publicclassStringDemopublicstaticvoidmain(String[]args)//定义一个字符串//Stringstr="abc";//Str... 查看详情

字节跳动又失一员大将，字节跳动ailab总监李磊离职加入ucsb

近日，字节跳动AI实验室总监李磊发布推特称将加盟加州大学圣巴巴拉分校（UCSB），重返学术界。事件起源于7月6日，AI研究者王威廉突然发推祝贺李磊加入UCSB，进入加州大学圣巴巴拉分校（UCSB）... 查看详情

迅猛扩张的字节跳动，踢到了一些铁板

边裁员边扩张，字节跳动究竟在下一盘什么棋？字节跳动堪称成长最快速的互联网企业之一。10月20日，据福布斯的实时富豪榜显示，字节跳动创始人张一鸣身价达到594亿美元，一举超过马化腾，成为中国... 查看详情

脉脉互联网人才报告：名校毕业生首选字节跳动腾讯华为居前三

...联网新人职业选择报告2021》揭晓了答案。报告显示，字节跳动最受C9名校毕业生欢迎，其次是腾讯，华为位列第三，微软成为唯一一家进入前十的外资企业。C9全称为“九校联盟”，是中国首个顶尖大学间的高... 查看详情

tyvjp2044["扫地"杯iiiday2]旅游景点

二次联通门: TyvjP2044["扫地"杯IIIday2]旅游景点 /*TyvjP2044["扫地"杯IIIday2]旅游景点并查集先把大于K的点合并再从头扫一遍若当前边的两边不在同一个集合就合并否则就割掉这条边*/#include<cstdio>#include<iostrea... 查看详情

css3动画的使用图片上下循环跳动

animation动画使用图片上下循环跳转html代码：<divclass="siteicon"> <imgsrc="./siteicon.png"alt=""> <p>点击跳转</p> </div>css代码：@keyframesicon{ 0%{opacity:0.8; 查看详情

f题：无线话筒扩音系统（本科）--2018年ti杯大学生电子设计竞赛

F题：无线话筒扩音系统（本科）--2018年TI杯大学生电子设计竞赛文章目录F题：无线话筒扩音系统（本科）--2018年TI杯大学生电子设计竞赛1、任务2、要求3、说明1、任务设计制作一个短距无线话筒扩音系统&#... 查看详情

d题：手势识别装置--2018年ti杯大学生电子设计竞赛

D题：手势识别装置–2018年TI杯大学生电子设计竞赛文章目录D题：手势识别装置--2018年TI杯大学生电子设计竞赛1．任务2．要求3．说明1．任务基于TI公司传感芯片FDC2214设计制作一个手势识别装置，实现... 查看详情

c题：无线充电电动小车（本科）--2018年ti杯大学生电子设计竞赛

C题：无线充电电动小车（本科）–2018年TI杯大学生电子设计竞赛文章目录C题：无线充电电动小车（本科）--2018年TI杯大学生电子设计竞赛1、任务2、要求3．说明1、任务设计并制作一个无线充电电动车&#... 查看详情

a题：电流信号检测装置（本科）--2018年ti杯大学生电子设计竞赛

A题：电流信号检测装置（本科）--2018年TI杯大学生电子设计竞赛文章目录A题：电流信号检测装置（本科）--2018年TI杯大学生电子设计竞赛1、任务2、要求3、说明1、任务如图1所示，由任意波信号发生器... 查看详情

b题：灭火飞行器（本科）--2018年ti杯大学生电子设计竞赛

B题：灭火飞行器（本科）--2018年TI杯大学生电子设计竞赛文章目录B题：灭火飞行器（本科）--2018年TI杯大学生电子设计竞赛1、任务2、要求3．说明1、任务基于四旋翼飞行器设计一个灭火飞行器（简... 查看详情