1.砝码称重
#include <iostream>
#include <vector>
using namespace std;
const int N=110;
const int M=100010;
int w[N];
int n;
int f[N][M];
int m;
int ans;
//f[i][j]表示到第i个砝码进行放置时的称得的重量为j的方案数
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
m+=w[i];
}
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j]+f[i-1][j+w[i]]+f[i-1][abs(j-w[i])];
}
}
for(int j=1;j<=m;j++)
{
if(f[n][j])//有方案
{
ans++;
}
}
cout<<ans<<endl;
return 0;
}2.直线
#include <iostream>
#include <map>
using namespace std;
struct node
{
double x,y;//使用double为了计算斜率和截距方便
}p[20*21+5];
map<pair<double,double>,int>mp;//判断是否已经有此直线了
int cnt;
int ans;
int main()
{
//20*21个整点即20行x19列
int row=21;//纵坐标0~20
int col=20;//横坐标0~19
for(int i=0;i<col;i++)
{
for(int j=0;j<row;j++)
{
p[cnt].x=i;
p[cnt].y=j;
cnt++;
}
}
ans=row+col;//初始为所有横线＋竖线
for(int i=0;i<cnt;i++)//枚举所有两两点
{
for(int j=0;j<cnt;j++)
{
if(p[i].x==p[j].x||p[i].y==p[j].y)continue;//同一横和竖都不要
double k=(p[i].y-p[j].y)/(p[i].x-p[j].x);
double b=(p[i].x*p[j].y-p[j].x*p[i].y)/(p[i].x-p[j].x);
if(mp[{k,b}]==0)
{
mp[{k,b}]=1;
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}3.异或数列
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int res=0;
vector<int>v(32);
for(int i=0;i<n;i++)
{
int k;
cin>>k;
res^=k;
for(int j=0;j<32&&k;j++)
{
if(k&1)
{
v[j]++;
}
k>>=1;
}
}
if(res==0)
{
cout<<0<<endl;
continue;
}
for(int j=31;j>=0;j--)
{
if(v[j]%2==0)continue;
else
{
if(v[j]==1)
{
cout<<1<<endl;
break;
}
else
{
if(n%2==0)
{
cout<<-1<<endl;
break;
}
else
{
cout<<1<<endl;
break;
}
}
}
}
}
return 0;
}4.左孩子右兄弟
#include <iostream>
#include <vector>
using namespace std;
const int N=1e5+10;
vector<int>e[N];
int n;
int dfs(int x)
{
int res=0;//子树的最大高度
for(int i=0;i<e[x].size();i++)
{
int v=e[x][i];
res=max(res,dfs(v));
}
return res+e[x].size();
}
int main()
{
cin>>n;
for(int i=2;i<=n;i++)
{
int fa;
cin>>fa;
//fa->i
e[fa].push_back(i);
}
cout<<dfs(1)<<endl;
return 0;
}5.时间显示
#include <iostream>
using namespace std;
#define ll long long
int main()
{
ll n;
cin>>n;
n/=1000;
ll h=n/3600;
n%=3600;
ll m=n/60;
n%=60;
ll s=n;
h%=24;
if(h<10)cout<<"0";
cout<<h<<":";
if(m<10)cout<<"0";
cout<<m<<":";
if(s<10)cout<<"0";
cout<<s<<endl;
return 0;
}6.通电
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=1000000+10;//1e6!!
struct edge
{
int u,v;
double d;
bool operator < (const edge &e)const{
return d<e.d;
}
};
struct point
{
int x,y,h;
};
int n;
edge e[2*N+10];
point p[N];
int fa[N];
int find(int x)
{
if(x!=fa[x])fa[x]=find(fa[x]);
return fa[x];
}
void Kruscal(int m)
{
double sum=0;
for(int i=0;i<n;i++)
{
fa[i]=i;
}
for(int i=0;i<m;i++)
{
int u=e[i].u;
int v=e[i].v;
double d=e[i].d;
int pu=find(u);
int pv=find(v);
if(pu!=pv)
{
fa[pu]=pv;
sum+=d;
}
}
printf("%.2lf\n",sum);
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int x,y,h;
cin>>x>>y>>h;
p[i]={x,y,h};
}
int idx=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
e[idx].u=i;
e[idx].v=j;
e[idx].d=sqrt(1.0*(p[i].x-p[j].x)*(p[i].x-p[j].x)+1.0*(p[i].y-p[j].y)*(p[i].y-p[j].y))+(p[i].h-p[j].h)*(p[i].h-p[j].h);
idx++;
}
}
sort(e,e+idx);
Kruscal(idx);
return 0;
}7.数位递增的数
#include <iostream>
using namespace std;
bool check(int x)
{
int d=x%10;
x/=10;
while(x!=0)
{
if(x%10>d)return false;
d=x%10;
x/=10;
}
return true;
}
int main()
{
int n;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)
{
if(check(i))ans++;
}
cout<<ans<<endl;
return 0;
}8.三元组中心问题
#include <iostream>
#include <map>
using namespace std;
const int N=1e6+10;
int a[N];
int ans=0;
map<int,int>mp;
int main()
{
//严格递增数列长度为3
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if(a[i]<a[j]&&a[j]<a[k])
{
if(!mp[j])
{
mp[j]=1;
ans++;
break;
}
}
}
}
}
cout<<ans<<endl;
return 0;
}9.音节判断
#include <iostream>
#include <map>
using namespace std;
map<char,int>mp;
int main()
{
for(char i='a';i<='z';i++)
{
if(i=='a'||i=='e'||i=='i'||i=='o'||i=='u')
{
mp[i]=1;
}
}
string s;
cin>>s;
string pd;
//fu yuan fu yuan 0辅1元
for(int i=0;i<s.size();i++)
{
if(mp[s[i]])
{
pd+="1";
while(mp[s[i]])
{
i++;
}
i--;
}
else
{
pd+="0";
while(!mp[s[i]])
{
i++;
}
i--;
}
}
if(pd=="0101")
{
cout<<"yes";
}
else{
cout<<"no";
}
return 0;
}10.长草
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define x first
#define y second
const int N=1000+100;
char g[N][N];
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
int n,m,k;
int ans;
void bfs()
{
queue<pii>q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(g[i][j]=='g')
{
q.push({i,j});
}
}
}
while(!q.empty())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=dx[i]+t.x;
int yy=dy[i]+t.y;
if(xx<1||xx>n||yy<1||yy>m||g[xx][yy]=='g')continue;
g[xx][yy]='g';
}
}
}
int main()
{
cin>>n>>m;
int stx=0;
int sty=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
if(g[i][j]=='g')
{
stx=i;
sty=j;
}
}
}
cin>>k;
while(k--)
bfs();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<g[i][j];
}
cout<<endl;
}
return 0;
}11.积木
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1000+5;
int n,m;
int a[N][N];
int H;
vector<int>seq;
long long sum;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]>=1)
{
seq.push_back(a[i][j]);
}
}
}
cin>>H;
sort(seq.rbegin(),seq.rend());
for(int h=1;h<=H;h++)
{
if(seq.back()>=h)
{
sum+=seq.size();
}
while(seq.back()<=h)
{
if(seq.size()==1)break;
seq.erase(seq.end()-1);
}
cout<<sum<<endl;
}
return 0;
}12.植树（DFS难）
#include <iostream>
#include <cmath>
using namespace std;
const int N=10000+100;
struct tree
{
int x,y,r,s;
};
int n;
tree v[N];
int vis[N];//有无加入答案
bool cross[N][N];
int ans;
double dis(int x,int y)
{
return sqrt(x*x+y*y);
}
void dfs(int cnt,int area)
{
if(cnt>=n)
{
ans=max(ans,area);
return;
}
for(int i=0;i<cnt;i++)//看看前面放进去的会不会和当前这棵树相交
{
if(vis[i]&&cross[i][cnt])
{
dfs(cnt+1,area);//有相交就不要
return;
}
}
//要和不要都要进行
vis[cnt]=1;
dfs(cnt+1,area+v[cnt].s);
vis[cnt]=0;
dfs(cnt+1,area);
return;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int x,y,r;
cin>>x>>y>>r;
v[i]={x,y,r,r*r};
}
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
double d=dis(v[i].x-v[j].x,v[i].y-v[j].y);
if(d<1.0*(v[i].r+v[j].r))cross[i][j]=cross[j][i]=1;
else cross[i][j]=cross[j][i]=0;
}
}
dfs(0,0);
cout<<ans<<endl;
return 0;
}13.子串分值
#include <iostream>
#include <map>
using namespace std;
#define ll long long
const int N=1e5+5;
ll last[N];
ll pre[N];
ll nex[N];
ll sum;
int main()
{
string s;
cin>>s;
int l=s.size();
for(int i=0;i<26;i++)
{
last[i]=-1;//求pre
}
for(int i=0;i<l;i++)
{
int k=s[i]-'a';
pre[i]=last[k];//当前下标的字符的上一个相同字符位置赋值
last[k]=i;//更新当前字符的下标
}
for(int i=0;i<26;i++)
{
last[i]=l;//求next
}
for(int i=l-1;i>=0;i--)
{
int k=s[i]-'a';
nex[i]=last[k];//当前下标的字符的下一个相同字符位置赋值
last[k]=i;
}
for(int i=0;i<l;i++)
{
sum+=(i-pre[i])*(nex[i]-i);
}
cout<<sum<<endl;
return 0;
}14.平面切分
//第一条直接增加的平面是2，以后每增加一条线，平面数量就加一（平行情况）
//若有交点，n个交点就加上n个平面
#include <iostream>
#include <set>
using namespace std;
//第一条直接增加的平面是2，以后每增加一条线，平面数量就加一（平行情况）
//若有交点，n个交点就加上n个平面
const int N=1000+10;
#define x first
#define y second
long double s[N][2];//存斜率和截距
long long ans;
bool st[N];//判重边
pair<long double,long double>p;//点的横坐标和纵坐标
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)//枚举每条边
{
cin>>s[i][0]>>s[i][1];
//用set自动去重
set<pair<long double,long double>>points;
for(int j=0;j<i;j++)//i这条边与前面的j条边进行比较
{
if(st[j])continue;
if(s[i][0]==s[j][0])
{
if(s[i][1]==s[j][1])
{
st[i]=1;
break;
}
else continue;
}
else
{
//y=k1*x+b1 y=k2*x+b2
//(b2-b1)=(k1-k2)x
//交点的横坐标
p.x=(s[j][1]-s[i][1])/(s[i][0]-s[j][0]);
//交点的纵坐标
p.y=s[i][0]*p.x+s[i][1];
points.insert(p);
}
}
if(!st[i])ans+=points.size()+1;//点的数量加上此条边的数量1
}
cout<<ans+1;//加上第一条边的多1
return 0;
}
