输入x，y，c， 找到任意一对a,b 使得a+b==c&& 0<=a<=x && 0<=b<=y
注意后两个条件，顺序搞错wa几次
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int x,y,c;
while(~scanf("%d%d%d",&x,&y,&c)){
if(x+y<c){
puts("Impossible");
continue;
}
int a,b;
bool s=false;
if(x>y){
s=true;
swap(x,y);
}
if(x>=c){
a=c;
b=;
}
else{
a=x;
b=c-x;
}
if(s) swap(a,b);
printf("%d %d\n",a,b);
}
return ;
}
无向图，边权都是1,人从s到f，走最短路，最短路可能有多条。强盗在r，强盗要抢劫的距离是从r到人走的路径的最近距离。因为可能有多条最短路，所以要求强盗到达每条最短路到最近距离，输出其中最大的。
做法 预处理出s到每个点到距离，r到每个点到距离。然后从s开始bfs，step记录的是步数，val记录的是这条路径上距离r的最近距离。
#include<cstdio>
#include<cstring>
#include<queue>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M=1e5+;
struct G {
struct E {
int v,next;
} e[M<<];
int le,head[M];
void init() {
le=;
mt(head,-);
}
void add(int u,int v) {
e[le].v=v;
e[le].next=head[u];
head[u]=le++;
}
} g;
bool vis[M];
void bfs(int s,int d[]) {
mt(vis,);
vis[s]=true;
queue<int> q;
while(!q.empty()) q.pop();
q.push(s);
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=g.head[u]; ~i; i=g.e[i].next) {
int v=g.e[i].v;
if(!vis[v]) {
vis[v]=true;
d[v]=d[u]+;
q.push(v);
}
}
}
}
int sd[M],rd[M],d[M],ans;
struct Q {
int step,val,id;
} now,pre;
queue<Q> q;
void solve(int s,int f) {
ans=;
mt(d,);
now.step=;
now.id=s;
now.val=rd[s];
while(!q.empty()) q.pop();
q.push(now);
while(!q.empty()) {
pre=q.front();
q.pop();
if(pre.id==f) {
ans=max(ans,pre.val);
continue;
}
int u=pre.id;
for(int i=g.head[u]; ~i; i=g.e[i].next) {
int v=g.e[i].v;
now.val=min(pre.val,rd[v]);
now.step=pre.step+;
if(now.step==sd[v]&&d[v]<now.val) {
d[v]=now.val;
now.id=v;
q.push(now);
}
}
}
}
int main() {
int n,m,u,v,s,f,r;
while(~scanf("%d%d",&n,&m)) {
g.init();
while(m--) {
scanf("%d%d",&u,&v);
g.add(u,v);
g.add(v,u);
}
scanf("%d%d%d",&s,&f,&r);
bfs(s,sd);
bfs(r,rd);
solve(s,f);
printf("%d\n",ans);
}
return ;
}
vector存图会慢一些
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M=1e5+;
vector<int> g[M];
bool vis[M];
void bfs(int s,int d[]) {
mt(vis,);
vis[s]=true;
queue<int> q;
while(!q.empty()) q.pop();
q.push(s);
while(!q.empty()) {
int u=q.front();
q.pop();
int len=g[u].size();
for(int i=; i<len; i++) {
int v=g[u][i];
if(!vis[v]) {
vis[v]=true;
d[v]=d[u]+;
q.push(v);
}
}
}
}
int sd[M],rd[M],d[M],ans;
struct Q {
int step,val,id;
} now,pre;
queue<Q> q;
void solve(int s,int f) {
ans=;
mt(d,);
now.step=;
now.id=s;
now.val=rd[s];
while(!q.empty()) q.pop();
q.push(now);
while(!q.empty()) {
pre=q.front();
q.pop();
if(pre.id==f) {
ans=max(ans,pre.val);
continue;
}
int u=pre.id;
int len=g[u].size();
for(int i=; i<len; i++) {
int v=g[u][i];
now.val=min(pre.val,rd[v]);
now.step=pre.step+;
if(now.step==sd[v]&&d[v]<now.val) {
d[v]=now.val;
now.id=v;
q.push(now);
}
}
}
}
int main() {
int n,m,u,v,s,f,r;
while(~scanf("%d%d",&n,&m)) {
for(int i=;i<=n;i++) g[i].clear();
while(m--) {
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
scanf("%d%d%d",&s,&f,&r);
bfs(s,sd);
bfs(r,rd);
solve(s,f);
printf("%d\n",ans);
}
return ;
}
手机排名按照出现次数，次数相同按照最低价格
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
string a,b;
map<string,int> num,val;
map<string,int>::iterator it;
struct G{
string a;
int num,val;
friend bool operator <(const G &a,const G &b){
return a.num>b.num||(a.num==b.num&&a.val<b.val);
}
}now;
vector<G> g;
int cost;
int main(){
num.clear();
val.clear();
for(int i=;i<;i++){
cin>>a>>b>>cost;
num[b]++;
if(val[b]){
val[b]=min(val[b],cost);
}
else{
val[b]=cost;
}
}
g.clear();
for(it=num.begin();it!=num.end();it++){
now.a=it->first;
now.num=it->second;
now.val=val[now.a];
g.push_back(now);
}
sort(g.begin(),g.end());
cout<<g[].a<<endl;
return ;
}
最多4个连续的能满足的 88 89 90 91
#include<cstdio>
int main(){
int n,ans[]={,,,};
while(~scanf("%d",&n)){
if(n<){
for(int i=;i<n;i++){
printf("%02d ",ans[i]);
}
}
else{
printf("Glupenky Pierre");
}
puts("");
}
return ;
}
汗诺塔，一开始都在A ，要移动成输入的状态，需要几步，每次都是考虑最下面的一个，然后相当于把n-1个移开，然后把第n个移动到目标处，移动n个需要2^n-1,把最后一个放到目标需要1
#include<cstdio>
typedef long long LL;
const int M=;
char a[M];
LL p[M];
int main(){
p[]=;
for(int i=;i<M;i++){
p[i]=p[i-]*;
}
int n;
while(~scanf("%d%s",&n,a)){
LL ans=;
int id=;
for(int i=n;i>=;i--){
int his=a[i-]-'A';
if(his==id) continue;
ans+=p[i-];
id=^^^id^his;
}
printf("%lld\n",ans);
}
return ;
}
n人分k队，不同队之间的人要打一场比赛，问最多能打几场，把人平均分k份打得最多
#include<cstdio>
int main(){
int t,n,k,ans;
while(~scanf("%d",&t)){
while(t--){
scanf("%d%d",&n,&k);
int x=n/k;
int y=n%k;
ans=y*(x+)*(n-x-)+(k-y)*x*(n-x);
printf("%d\n",ans/);
}
}
return ;
}
最多存在k种不同字母，问最多几个，有几种方法达到最多
最多几个就是把前k种加起来
方法数就是有几种个数和第k种一样，那么从中选几种
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M=1e5+;
char a[M];
int num[];
int C[][];
int main(){
for(int i=;i<;i++){
C[i][i]=;
C[i][]=;
}
for(int i=;i<;i++){
for(int j=;j<i;j++){
C[i][j]=C[i-][j]+C[i-][j-];
}
}
int k;
while(~scanf("%s%d",a,&k)){
mt(num,);
for(int i=;a[i];i++){
num[a[i]-'a']++;
}
sort(num,num+);
int sum=;
int kk=;
for(int i=;i>=;i--){
sum+=num[i];
kk++;
if(kk==k) break;
}
printf("%d ",sum);
if(k==){
puts("");
continue;
}
if(num[-k]==){
puts("");
continue;
}
if(num[-k-]!=num[-k]){
puts("");
continue;
}
int cn=,cm=;
for(int i=;i<;i++){
if(num[i]==num[-k]){
cn++;
}
}
for(int i=-k;i<;i++){
if(num[i]==num[-k]){
cm++;
}
}
printf("%d\n",C[cn][cm]);
}
return ;
}
end