AC代码:
- #include
- #include
- #include
- #include
- #define endl '\n'
- #define int long long
- using namespace std;
- typedef long long ll;
- int a,b,c;
- void solve() {
- cin>>a>>b>>c;
- int diff=abs(a-b);
- if(diff==0){
- cout<<0<
- return;
- }
- if(diff<=c*2) {
- cout<<1<
- return;
- }
- cout<
2)+(diff%(c*2)!=0)< - }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int t=1;
- cin>>t;
- while(t--) {
- solve();
- }
- return 0;
- }
B.The Corridor or There and Back Again
二分
AC代码:
- #include
- #include
- #include
- #include
- #define endl '\n'
- //#define int long long
- using namespace std;
- typedef long long ll;
- const int N=110;
- int d[N],s[N];
- int n;
- bool check(int x){
- for(int i=n;i>=1;i--){
- if(2*(x-d[i])>=s[i]) return false;
- }
- return true;
- }
- void solve() {
- cin>>n;
- for(int i=1;i<=n;i++) cin>>d[i]>>s[i];
- int l=1,r=1000;
- while(l
- int mid=(l+r+1)/2;
- // cout<
- if(check(mid)) l=mid;
- else r=mid-1;
- }
- cout<
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int t=1;
- cin>>t;
- while(t--) {
- solve();
- }
- return 0;
- }
素数分解成两个数的和,这两个数的最大公约数一定是1
如果两者有公约数,那么该也有不为1的约数,就不是素数了
AC代码:
- #include
- #include
- #include
- #include
- #define endl '\n'
- //#define int long long
- using namespace std;
- typedef long long ll;
- const int N=1e7+10;
- int prime[N];
- int vis[N];
- bool st[N];
- int cnt;
- //欧拉筛
- void get_prime(int n){
- for(int i=2;i<=n;i++){
- if(!st[i]) prime[cnt++]=i;
- for(int j=0;prime[j]<=n/i;j++){
- st[prime[j]*i]=true;
- if(i%prime[j]==0) break;
- }
- }
- }
- void solve() {
- int l,r;
- cin>>l>>r;
- //如果有偶数(除了2)的话
- if(r-l>=1){
- for(int i=l;i<=r;i++){
- if(i%2==0&&i!=2){
- cout<<2<<' '<-2<
- return;
- }
- }
- }
- //其它的情况都是只有一个数,判断一个数即可
- if(l==r){
- // //如果是素数,直接输出-1
- // if(vis[l]){
- // cout<<-1<
- // return;
- // }
- //如果是偶数
- if(l%2==0&&l!=2){
- cout<<2<<' '<
-2< - return;
- }
- else{
- for(int i=3;i<=l/i;i+=2){
- if(l%i==0){
- cout<
' '< - return;
- }
- }
- }
- }
- cout<<-1<
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- get_prime(N);
- for(int i=0;i
1; - // for(int i=0;i
- int t=1;
- cin>>t;
- while(t--) {
- solve();
- }
- return 0;
- }
AC代码:
- #include
- #include
- #include
- #include
- #define endl '\n'
- //#define int long long
- using namespace std;
- typedef long long ll;
- const int N=1e7+10;
- int prime[N];
- int vis[N];
- bool st[N];
- int cnt;
- //欧拉筛
- void get_prime(int n){
- for(int i=2;i<=n;i++){
- if(!st[i]) prime[cnt++]=i;
- for(int j=0;prime[j]<=n/i;j++){
- st[prime[j]*i]=true;
- if(i%prime[j]==0) break;
- }
- }
- }
- void solve() {
- int l,r;
- cin>>l>>r;
- //如果有偶数(除了2)的话
- if(r-l>=1){
- for(int i=l;i<=r;i++){
- if(i%2==0&&i!=2){
- cout<<2<<' '<-2<
- return;
- }
- }
- }
- //其它的情况都是只有一个数,判断一个数即可
- if(l==r){
- //如果是素数,直接输出-1
- if(vis[l]){
- cout<<-1<
- return;
- }
- //如果是偶数
- if(l%2==0&&l!=2){
- cout<<2<<' '<
-2< - return;
- }
- else{
- for(int i=3;i<=l/i;i+=2){
- if(l%i==0){
- cout<
' '< - return;
- }
- }
- }
- }
- cout<<-1<
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- get_prime(N);
- for(int i=0;i
1; - // for(int i=0;i
- int t=1;
- cin>>t;
- while(t--) {
- solve();
- }
- return 0;
- }
AC代码:
- #include
- #include
- #include
- #include
- #define endl '\n'
- #define int long long
- using namespace std;
- typedef long long ll;
- int n,x,y;
- int gcd(int a,int b){
- if(b==0) return a;
- return gcd(b,a%b);
- }
- void solve() {
- cin>>n>>x>>y;
- int cnt1=n/x;
- int cnt2=n/y;
- int cnt3=n/(x*y/gcd(x,y));
- cnt1=cnt1-cnt3;
- cnt2=cnt2-cnt3;
- int sum2=(1+cnt2)*cnt2/2;
- int sum1=(2*n+1-cnt1)*cnt1/2;
- cout<
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int t=1;
- cin>>t;
- while(t--) {
- solve();
- }
- return 0;
- }
利用前缀异或和,pre[i]表示从a[1]一直异或到a[i]
ans0将所有s中为0对应的a值异或起来,之后ans0也将不断地变化,始终为所有s中为0对应的a值异或起来
ans1将所有s中下标为1对应的a值异或起来,之后ans1也将不断地变化,始终为所有s中为1对应的a值异或起来
当op等于2时,直接输出ans0或者ans1即可
那么当op等于1时,我们就要考虑如何变化ans0和ans1了,每次都是[l,r]进行01互换,那么相应地,ans0和ans1也会变化
由于只有[l,r]区间变化,所以我们也只考虑[l,r]这一区间
我们将ans0异或上a[l]^a[l+1]^...a[r],如果ans0中的项有该区间以外的,那么仍异或上,如果项有该区间里面的,那么就消掉,如果区间有项是ans0没有的,也异或上
ans1同理
这样就实现了每次异或的项的转换
AC代码:
- #include
- #include
- #include
- #include
- #define endl '\n'
- //#define int long long
- using namespace std;
- const int N=1e5+10;
- int a[N];
- int pre[N];
- int n,q;
- void solve() {
- cin>>n;
- for(int i=1;i<=n;i++) {
- cin>>a[i];
- pre[i]=pre[i-1]^a[i];
- }
- string s;
- cin>>s;
- s=' '+s;
- int ans0=0,ans1=0;
- for(int i=1;i<=n;i++){
- if(s[i]=='0') ans0^=a[i];
- else ans1^=a[i];
- }
- cin>>q;
- while(q--){
- int op;
- cin>>op;
- if(op==1){
- int l,r;
- cin>>l>>r;
- int ans=pre[r]^pre[l-1];
- ans0^=ans;
- ans1^=ans;
- }
- else{
- int x;
- cin>>x;
- if(x==0) cout<
' '; - else cout<
' '; - }
- }
- cout<
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int t=1;
- cin>>t;
- while(t--) {
- solve();
- }
- return 0;
- }
拓扑排序+dfs
首先进行拓扑排序,将那些没有成环的排好序,然后对于成环的,用dfs搜索环中价值最小的,将其放在最后
AC代码:
- #include
- #include
- #include
- #include
- #include
- #include
- #define endl '\n'
- //#define int long long
- using namespace std;
- const int N=1e5+10;
- int a[N],c[N];
- int d[N];
- bool ok[N];
- int n;
- int minn,mini;
- void dfs(int x) {
- if(ok[x]) return;
- ok[x]=true;
- if(minn>c[x]) {
- minn=c[x];
- mini=x;
- }
- dfs(a[x]);
- }
- void solve() {
- cin>>n;
- //初始化
- for(int i=1; i<=n; i++) {
- d[i]=0;
- ok[i]=false;
- }
- for(int i=1; i<=n; i++) {
- cin>>a[i];
- d[a[i]]++;//入度+1
- }
- for(int i=1; i<=n; i++) cin>>c[i];
- queue<int>q;
- vector<int>ans;
- for(int i=1; i<=n; i++) {
- if(d[i]==0) {
- q.push(i);
- }
- }
- while(q.size()) {
- int t=q.front();
- q.pop();
- ans.push_back(t);
- ok[t]=true;//表示t已经排好了
- d[a[t]]--;
- if(d[a[t]]==0) q.push(a[t]);
- }
- if(ans.size()
- for(int i=1; i<=n; i++) {
- if(!ok[i]) {
- minn=c[i],mini=i;
- dfs(i);
- int x=a[mini];
- ans.push_back(x);
- x=a[x];
- while(x!=a[mini]) {
- ans.push_back(x);
- x=a[x];
- }
- }
- }
- }
- for(auto v:ans) cout<
' '; - cout<
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int t=1;
- cin>>t;
- while(t--) {
- solve();
- }
- return 0;
- }
-
相关阅读:
YOLOv5的Tricks | 【Trick10】从PyTorch Hub加载YOLOv5
Spring Security学习笔记(一)Spring Security架构原理
HTTPSConnectionPool(host=‘files.pythonhosted.org‘, port=443): Read timed out解决
Three.js 进阶之旅:全景漫游-高阶版在线看房 🏡
面试所必问的技术点,你都知道吗?
docker入门(二)—— docker三大概念(镜像、容器、仓库)
GNN 101
身份证合法验证查询易语言代码
肝了一星期,终于把堆的创建、插入、删除和堆排序肝完了(超详细图文讲解)
Ubuntu镜像源cn.arichinve.ubuntu.com不可用原因分析和解决
-
原文地址:https://blog.csdn.net/m0_74087709/article/details/132792563