1.签到:https://ac.nowcoder.com/acm/contest/82526/A
AC代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin>>n;
cout<<n/3;
}
2.思维:https://ac.nowcoder.com/acm/contest/82526/B
就是判断最多有几个相等:
#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
bool cmp(int a,int b)
{
return a<b;
}
int cnt=1;
int ans=1;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1,cmp);
for(int i=2;i<=n;i++)
{
if(a[i]==a[i-1])
{
cnt++;
ans=max(ans,cnt);
}
else
{
cnt=1;
}
}
cout<<ans;
}
3.思维:https://ac.nowcoder.com/acm/contest/82526/C
从后往前找到第一个不是0的位置,变成99999000的形式再+1即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int t;
char s[1000010];
int main()
{
cin>>t;
while(t--)
{
scanf("%s",s);
int f=0;
for(int i=strlen(s)-1;i>=1;i--)
{
if(s[i]!='0')
{
f=1;
break;
}
}
if(f==0)
{
cout<<0<<endl;
continue;
}
long long cnt=0;
int cn=0;
for(int i=strlen(s)-1;i>=1;i--)
{
if(cn==0&&s[i]=='0')continue;
if(s[i]!='0') cn=1;
cnt+='9'-s[i];
}
cout<<cnt+1<<endl;
}
}
4.枚举:https://ac.nowcoder.com/acm/contest/82526/D
对于1-1e5的数据,我们先暴力枚举一下发现最多128个因子,于是我们就直接用前缀和维护即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[100010];
int sum[100010][150];
int query(int ck)
{
int cnt=0;
for(int i=1;i*i<=ck;i++)
{
if(ck%i==0&&ck/i==i) cnt++;
else if(ck%i==0) cnt+=2;
}
return cnt;
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=130;j++) sum[i][j]=sum[i-1][j];
int c=query(a[i]);
sum[i][c]++;
}
while(q--)
{
int l,r;
cin>>l>>r;
long long ans=0;
for(int i=1;i<=130;i++)
{
long long cc=sum[r][i]-sum[l-1][i];
ans+=cc*(cc-1)/2;
}
cout<<ans<<endl;
}
}
5.构造:https://ac.nowcoder.com/acm/contest/82526/E
首先2不是合数,并且同奇偶的数加起来一定是合数(出了1+1),于是我们考虑每一个下标i对应i+4,这样前边的n-4个数就一定符合条件,对于后面4个数,分奇偶讨论即可,下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin>>n;
if (n < 8) {
cout << -1;
return 0;
}
for (int i = 5; i <= n; i++)
cout << i << ' ';
if (n & 1) {
cout << "2 1 4 3" << '\n';
}
else {
cout << "1 2 3 4" << '\n';
}
}
6.DFS,图论:https://ac.nowcoder.com/acm/contest/82526/F
(本代码是参考雨巨的思路,有一些更加简单的可以直接看其他人代码)
首先我们分类讨论一下:
1.删的边在环上并且在得到1--n的路径上,那么就换成环的另一段即可。
2.删的边不在环上也不在路径上,无影响。
3.删的边在环上但是不在路径上直接输出。
4删的边在路径上但是不在环上,输出-1.
于是我们只要维护环的长度,1--n的距离(不一定min),该距离走过的环的长度以及边的序号啊,环上的边。
如何得到环的长度:DFS,遇到vis过的说明找到了环,return vis过的值,这样倒着把所有环的点记录了一遍,到vis那里时令flag=0,以免让前面的分支也被算进。
再遍历一遍1--n的距离,用DFS找到一条有解的路径即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int> > edge[100010];
bool vis[100010];
bool b_huan[100010];//在环上的边
bool b_dist[100010];//在遍历dis中经过的环的边
int len,flag=1;
int sum,huan;
int dfs1(int x,int fa)
{
vis[x]=1;
for(int i=0;i<edge[x].size();i++)
{
int root=edge[x][i].first;
int mark=edge[x][i].second;
if(fa==root) continue;
if(vis[root])
{
b_huan[mark]=1;
return root;
}
int t=dfs1(root,x);
if(t)
{
if(flag)
{
b_huan[mark]=1;
len++;
}
if(t==x) flag=0;
return t;
}
}
return 0;
}
int dfs(int x)
{
vis[x]=1;
if(x==n) return 1;
for(int i=0;i<edge[x].size();i++)
{
int y = edge[x][i].first;
int num = edge[x][i].second;
if(vis[y]) continue;
if(!dfs(y)) continue;
sum++;
if(b_huan[num]) huan++;
b_dist[num]=1;
return 1;
}
return 0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int u,v;
cin>>u>>v;
edge[u].push_back({v,i});
edge[v].push_back({u,i});
}
//查找环上的边
dfs1(1,0);
len++;
memset(vis,0,sizeof(vis));
dfs(1);
int huanwai = sum - huan;
int huanother = len - huan;
for (int i = 1; i <= n; i++)
{
if (b_huan[i] == 1 && b_dist[i] == 1)
{
cout << huanwai + huanother<< endl;
}
else if (b_huan[i] == 1 && b_dist[i] == 0)
{
cout << huanwai + huan<< endl;
}
else if (b_huan[i] == 0 && b_dist[i] == 0)
{
cout << min(huanwai + huan, huanwai + huanother)<< endl;
}
else if (b_huan[i] == 0 && b_dist[i] == 1)
{
cout << -1<< endl;
}
}
}