A. Diversity
题意:给定字符串s,求至少换多少个字符,使得有k个不同的英文字母
思路: 有没有可能? 可能的话,是不是已经够了,还是不够?
#include<bits/stdc++.h>
#define bug cout <<"bug"<<endl
using namespace std;
typedef long long ll;
const int MAX_N=2000;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
map<char,int> mp;
int main(void){
char s[5000];
int k;
scanf("%s",s+1);cin >> k;
int len=strlen(s+1);
if(len<k){
cout <<"impossible"<<endl;
return 0;
}
else{
int cnt=0;
for(int i=1;i<=len;i++){
if(!mp[s[i]]) mp[s[i]]=1,cnt++;
}
if(cnt >= k) cout <<"0"<<endl;
else cout << k-cnt << endl;
}
}B. Rectangles
题意:给一个二维矩阵(0,1),求一集合,如果只有集合只包含一个元素,一定满足要求 ; 如果>=2,所有元素(都是0或者都是1)要求在同一行或者同一列
思路:求组合数,小心1的情况算了2次.. mmp 居然把组合数求错了找不出bug ... 没注意过c[50][25]的大小超过int范围又wa了一次,是真的菜
#include<bits/stdc++.h>
#define bug cout <<"bug"<<endl
using namespace std;
typedef long long ll;
const int MAX_N=2000;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int n,m;
ll ans1,ans0;
int a[60][60];
ll c[60][60];
void init(){
c[0][0]=c[1][0]=c[1][1]=1;
for(int i=2;i<=50;i++){
c[i][0]=1;
for(int j=1;j<=i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
void check1(){
for(int i=1;i<=n;i++){
int cnt0=0,cnt1=0;
for(int j=1;j<=m;j++){
if(a[i][j]==1) cnt1++;
else cnt0++;
}
if(cnt1>=2) for(int i=2;i<=cnt1;i++) ans1+=c[cnt1][i]/*,printf("c[%d][%d]=%d\n",cnt1,i,c[cnt1][i])*/;
if(cnt0>=2) for(int i=2;i<=cnt0;i++) ans0+=c[cnt0][i]/*,printf("c[%d][%d]=%d\n",cnt0,i,c[cnt0][i])*/;
}
return ;
}
void check2(){
for(int j=1;j<=m;j++){
int cnt0=0,cnt1=0;
for(int i=1;i<=n;i++){
if(a[i][j]==1) cnt1++;
else cnt0++;
}
if(cnt1>=2) for(int i=2;i<=cnt1;i++) ans1+=c[cnt1][i];
if(cnt0>=2) for(int i=2;i<=cnt0;i++) ans0+=c[cnt0][i];
}
return ;
}
int main(void){
init();
cin >> n >> m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
ll ans=n*m;
check1();
ans+=(ans1+ans0);
ans1=ans0=0;
check2();
ans+=(ans1+ans0);
cout << ans << endl;
return 0;
}思路:排序后给个序号,直接找环
#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int a[MAX_N],b[MAX_N];
bool vis[MAX_N];
map<int,int> mp,mp1;
vector <vector<int> > ans;
void check(int i){
vector <int> t;
int now=a[i];
if(now==i){
vis[i]=true;
t.push_back(i);
ans.push_back(t);
return ;
}
while(1){
if(vis[now]) {break;}
t.push_back(now);
vis[now]=true;
// printf("%d ~\n",now);
now=a[now];
}
ans.push_back(t);
return ;
}
int main(void){
int n;cin >> n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
mp[b[i]]=i,mp1[i]=b[i];
for(int i=1;i<=n;i++) a[i]=mp[a[i]];
for(int i=1;i<=n;i++){
if(!vis[a[i]]) check(i);
}
// for(int i=1;i<=n;i++) printf("%d ",a[i]);
cout << ans.size() <<endl;
for(int i=0;i<(int)ans.size();++i){
vector <int> t=ans[i];
cout << t.size() <<" ";
for(int j=0;j<(int)t.size();++j) printf("%d ",t[j]); puts("");
}
return 0;
}题意:交互题有一个升序排序,长度为n(1e5)的链表,每个节点有v,next . 最小值的编号为s,找到 所有>=x 中最小的值 , 且查询次数<=1999
思路:随机查询k次寻找 <=x中最靠近x的节点的next.保存mmax最大值.剩下1999-k次从next开始暴力搜索
找不到的概率为 (1-k/n)^(1999-k) 当k=1e3就非常的小. 我感觉很神奇 . 所谓的随机数算法
#include<bits/stdc++.h>
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
int a[MAX_N],b[MAX_N];
bool vis[MAX_N];
map<int,int> mp,mp1;
vector <vector<int> > ans;
int main(void){
srand(time(NULL));
ll n,s,x;
int v,ac;
cin >> n>>s >> x;
int mmax=-1,index=s;//index=s写index=-1 wa 8
for(int i=1;i<=1000;++i){
int t=((1LL)*rand()*1998+rand())%n+1;
printf("? %d\n",t);
fflush(stdout);
scanf("%d%d",&v,&ac);
if(v<=x && v>mmax) mmax=v,index=ac;
}
if(mmax==x){
printf("! %d\n",mmax);
return 0;
}
else{
while(index!=-1){
printf("? %d\n",index);
fflush(stdout);
scanf("%d%d",&v,&ac);
mmax=max(mmax,v);
if(mmax>=x) break;
index=ac;
}
}
if(mmax>=x) printf("! %d\n",mmax);
else printf("! %d\n",-1);
fflush(stdout);
return 0;
}
E. Upgrading Tree
溜了
京公网安备 11010502036488号