1 hello,world!
因为要有一个hello,world!,但不想是直接输出,所以加了个循环()。
#include<bits/stdc++.h>
using namespace std;
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cout<<"hello,world!"<<"\n";
}
}
2 乘积
当n等于m时n%m为0,故当n大于m时答案为零。
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m;
cin>>n>>m;
int ans=1ll;
if(n>=m){
ans=0ll;
}else{
for(int i=1;i<=n;i++){
ans=ans%m*i%m;
}
}
cout<<ans<<"\n";
}
3 最长序列
显然每段字符相同的子串中取一个字符即为答案。
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
string s;
cin>>s;
string res;
char ls='$';
for(auto &i:s){
if(i!=ls){
res.push_back(i);
}
ls=i;
}
cout<<res<<"\n";
}
4 碰撞
简化的高中物理题()。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e9l;
signed main(){
vector<pair<int,int>> p(2);
for(auto &[d,v]:p){
cin>>d>>v;
}
sort(p.begin(),p.end());
int ans=0;
if(p[0].first==p[1].first){
cout<<ans<<"\n";
return 0;
}
int sign=p[0].second*p[1].second;
if(sign>0){
int d=abs(p[0].first-p[1].first);
if(p[0].second>0){
ans=d+2*(inf-p[1].first);
}else{
ans=d+2*(p[0].first+inf);
}
}else if(sign<0){
if(p[0].second<0){
ans=2*inf+p[0].first+inf+inf-p[1].first;
}else{
ans=p[1].first-p[0].first;
}
}
cout<<ans<<"\n";
}
5 异或交换
两个数列交换同一个位置的数等价于异或和同时异或上这两个元素的异或和,故变化的位数的差的绝对值恒为零。
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n;
cin>>n;
for(int j=0;j<2;j++){
for(int i=1;i<=n;i++){
int tem;
cin>>tem;
}
}
cout<<0<<" "<<1<<" "<<0<<" "<<n<<"\n";
}
6 极彩色
对每个颜色的数量用前缀和维护即可。
#include<bits/stdc++.h>
using namespace std;
signed main(){
::ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,q;
cin>>n>>q;
vector<int> c(n+10);
for(int i=1;i<=n;i++){
cin>>c[i];
}
vector<vector<int>> sum(8,vector<int>(n+10));
for(int i=1;i<=n;i++){
for(int j=1;j<=7;j++){
sum[j][i]=sum[j][i-1];
}
sum[c[i]][i]++;
}
for(int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
int v=0;
for(int j=1;j<=7;j++){
if(sum[j][r]-sum[j][l-1]){
v++;
}
}
if(v==7){
cout<<1<<"\n";
}else{
cout<<0<<"\n";
}
}
}
7 约数个数为6
约数个数为6的数只会是形如的形式,其中p,q均为质数且不相等。
设小于等于n的质数有x个,答案即为x(x-1)+x,即为。
用质数筛求出质数数量即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
void oula(int n,vector<int>&p){
vector<int> v(n+10);
for(int i=2;i<=n;i++){
if(!v[i]){
p.push_back(i);
}
for(auto &j:p){
if(j*i>n){
break;
}
v[j*i]=1;
if(i%j==0){
break;
}
}
}
}
signed main(){
int n;
cin>>n;
vector<int> p;
oula(n,p);
int p_size=(int)p.size();
cout<<p_size*p_size;
}
8 干饭人,干饭魂!
背包。
由题意,猫娘到食堂可能是直接到,也可能是超过了食堂的位置再折返。
因为猫娘的速度是1m/s,所以猫娘在2m之后折返一定不是最优的方案。
所以我们对0-2m的路程进行一个背包,求出对应的最小时间,再补上猫娘步行到达食堂的时间即可。
这个背包其实会引入猫娘在越过食堂后还继续用瞬移符的方案,但是显然不会是最优,所以不会影响答案。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxx=1ll<<60;
signed main(){
int n,m;
cin>>n>>m;
vector<int> p(2*m+10,maxx);
p[0]=0;
for(int i=1;i<=n;i++){
int t,d;
cin>>t>>d;
for(int j=2*m;j>=d;j--){
p[j]=min(p[j],p[j-d]+t);
}
}
int ans=maxx;
for(int i=0;i<=2*m;i++){
ans=min(ans,p[i]+abs(i-m));
}
cout<<ans<<"\n";
}
9 1-连通块
经典bfs判连通
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct point{
int x,y;
};
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
signed main(){
int n,m;
cin>>n>>m;
vector<string> f(n+10);
for(int i=1;i<=n;i++){
cin>>f[i];
f[i]=" "+f[i];
}
vector<vector<int>> v(n+10,vector<int>(m+10));
int ans=0;
auto bfs=[&](int x,int y){
++ans;
v[x][y]=1;
queue<point> q;
q.push({x,y});
while(!q.empty()){
auto [nx,ny]=q.front();
q.pop();
for(int i=0;i<4;i++){
int lx=nx+dx[i],ly=ny+dy[i];
if(lx<1||lx>n||ly<1||ly>m||v[lx][ly]){
continue;
}
if(f[nx][ny]=='*'){
v[lx][ly]=1;
q.push({lx,ly});
}else{
if(f[lx][ly]=='*'){
v[lx][ly]=1;
q.push({lx,ly});
}
}
}
}
};
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(f[i][j]=='*'&&!v[i][j]){
bfs(i,j);
}
}
}
cout<<ans<<"\n";
}
10 求导
大模拟(其实也不大)
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
string s;
cin>>s;
if(s[0]!='-'){
s="+"+s;
}
string L;
vector<string> po;
vector<string> ne;
int z=0;
auto dec=[&](){
if(L.empty()||z==0){
return ;
}
if(z==1){
po.push_back(L);
}else if(z==-1){
ne.push_back(L);
}
L="";
};
for(auto &i:s){
if(i=='+'){
dec();
z=1;
}else if(i=='-'){
dec();
z=-1;
}else{
L+=i;
}
}
dec();
map<string,int> k;
for(auto &i:po){
string coe;
string sec;
int flag=1;
for(auto &j:i){
if(isdigit(j)&&flag){
coe.push_back(j);
}else{
flag=0;
sec.push_back(j);
}
}
if(!sec.empty()){
k[sec]+=coe.empty()?1:stoi(coe);
}
}
for(auto &i:ne){
string coe;
string sec;
int flag=1;
for(auto &j:i){
if(isdigit(j)&&flag){
coe.push_back(j);
}else{
flag=0;
sec.push_back(j);
}
}
if(!sec.empty()){
k[sec]-=coe.empty()?1:stoi(coe);
}
}
auto del=[&](int x){
return abs(x)==1?(x==1?"":"-"): to_string(x);
};
int num=0;
map<string,int> tra;
map<int,int,greater<>> x;
for(auto &[sec,coe]:k){
if(sec=="sinx"){
tra["cosx"]+=coe;
}else if(sec=="cosx"){
tra["sinx"]-=coe;
}else if(sec=="x"){
num+=coe;
}else{
string exp=string(sec.begin()+2,sec.end());
x[stoi(exp)-1]+=stoi(exp)*coe;
}
}
vector<string> ans;
for(auto &[exp,coe]:x){
if(exp==1){
ans.push_back(del(coe)+"x");
}else{
ans.push_back(del(coe)+"x^"+ to_string(exp));
}
}
if(tra["sinx"]){
ans.push_back(del(tra["sinx"])+"sinx");
}
if(tra["cosx"]){
ans.push_back(del(tra["cosx"])+"cosx");
}
if(num!=0){
ans.push_back(to_string(num));
}
if(ans.empty()){
cout<<0<<"\n";
return 0;
}
string res;
for(int i=0;i<ans.size();i++){
auto& sec=ans[i];
if(sec[0]=='-'){
res.append(sec);
continue;
}
if(i!=0){
res.push_back('+');
}
res.append(sec);
}
cout<<res;
}