题解 |
最后一个签到 还是个字符串基础题
https://ac.nowcoder.com/acm/contest/27150/B
A
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <cmath>
#include <string>
using namespace std;
int arr[110];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=0;i<n;i++){
int temp=0;
for(int j=0;j<i;j++){
if(arr[j]<arr[i]) temp++;
}
cout<<temp<<" ";
}
return 0;
}
B
#include<stdio.h>
#include<string.h>
#include<string.h>
#include<stdlib.h>
#include<stdlib.h>
int comp(const void* a, const void* b)//用来做比较的函数。
{
return *(long long int*)a - *(long long int*)b;
}
char s[100000];
long long int qc[100000];
long long int mod1 = 212370440130137957ll, ans=1;
long long int f;
int main() {
//freopen("2.in", " r ", stdin);
// freopen("2.out", " w ", stdout);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s", s);
f = 0;
int sl = strlen(s);
for (int j = 1; j <= sl; j++)
{
f = (f * 131 + (s[j - 1])) % mod1;
}
qc[i] = f;
}
qsort(qc, n, sizeof(long long int), comp);
for (int i = 1; i < n; i++)
{
if (qc[i] != qc[i - 1])
ans++;
}
printf("%lld", ans);
}
C
#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la, lb, j;
char a[MAXN], b[MAXN];
int main()
{
cin >> b + 1;
lb = strlen(b + 1);
for (int i = 2; i <= lb; i++)
{
while (j && b[i] != b[j + 1])
j = kmp[j];
if (b[j + 1] == b[i])j++;
kmp[i] = j;
}
for (int i = 1; i <= lb; i++)
cout << kmp[i] << " ";
return 0;
}
D
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
unordered_map<long long int,long long int>bcj,bcjzn;
long long int ZN, QC, N,Z ,Q,x,y,a[2100000],b[2100000], c[2100000],d;
long long int find(long long int f) {
return f == bcj[f] ? f : bcj[f] = find(bcj[f]);
}
int main() {
//freopen("1.in", " r ", stdin);
//freopen("1.out", " w ", stdout);
ios::sync_with_stdio(false);
cin >> N >> ZN >> QC>>Z >> Q;
if (N > 2e4 || N < 1 || ZN>2e4 || ZN < 1 || QC>2e4 || QC < 1 || Z > 2e4 || Z < 1 || Q>1e6||Q<1)
{
return -1;
}
for (int i = 0; i < N; i++)
{
cin >> a[i];
bcj[a[i]] = a[i];
if (a[i] > 1e18||a[i]<1) {
return -1;
}
}
for (int i = 0; i < ZN; i++)
{
cin >> b[i];
bcjzn[b[i]] = 1;
if (b[i] > 1e18 || b[i] < 1||bcj.find(b[i])==bcj.end()) {
return -1;
}
}
for (int i = 0; i < QC; i++) {
cin >> c[i];
if (c[i] > 1e18 || c[i] < 1 || bcj.find(c[i]) == bcj.end()) {
return -1;
}
long long int fx = find(c[0]);
long long int fy = find(c[i]);
if (fx != fy)
{
bcj[fy] = fx;
}
}
for (int i = 0; i < Z; i++) {
cin >> x>>y;
if (x > 1e18||x<1||y>1e18 || y < 1 || bcj.find(x) == bcj.end() || bcj.find(y) == bcj.end()) {
return -1;
}
long long int fx = find(x);
long long int fy = find(y);
if (fx != fy)
{
bcj[fx] = fy;
}
}
for (int i = 0; i < Q; i++) {
cin >> d;
if (d > 1e18 || d < 1 || bcj.find(d) == bcj.end()||bcjzn.find(d)==bcjzn.end()) {
return -1;
}
long long int fx = find(d);
long long int fy = find(c[0]);
if (fx != fy)
{
printf("ac\n");
}
else {
printf("wa\n");
}
}
}
E
#include<bits/stdc++.h>
using namespace std;
int n,v,a[10000],b[10000],dp[100000];
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++)
{
for(int j=a[i];j<=v;j++)
{
dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
}
}
cout<<dp[v];
}
F
#include<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
cin>>a>>b;
if(a.find(b)!=a.npos)
{
cout<<"YES";
}else
{
cout<<"NO";
}
}
G
#include<bits/stdc++.h>
using namespace std;
bool hs[110000000] = { 0 };
int ss[11000000] = { 0 }, sz, n = 100000000, sum[110000000], t;
int main() {
//freopen("10.in", " r ", stdin);
//freopen("10.out"," w ", stdout);
cin >> t;
if (t > 1e5)return -1;
for (int i = 2; i <= n; i++)
{
if (hs[i] == false)
{
ss[++sz] = i;
sum[i] = sum[i - 1] + 1;
}
else
{
sum[i] = sum[i - 1];
}
for (int j = 1; j <= sz && (long long int)i * (long long int)ss[j] <= n; j++)
{
hs[ss[j] * i] = 1;
if (i % ss[j] == 0)
{
break;
}
}
}
while (t--)
{
int q, p;
cin >> p >> q;
if (p > q)return -1;
if (q > 1e8 || q < 1 || p > 1e8 || p < 1)return -1;
cout << sum[q] - sum[p - 1] << endl;
}
return 0;
}
H
I
#include<iostream>
#include<algorithm>
using namespace std;
long long int n, m, t[500][500], sj[500];
long long int Q;
long long int up = 0;
void floy(int k) {
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
t[i][j] = min(t[i][k] + t[k][j], t[i][j]);
}
}
}
int main() {
cin >> n >> m>>Q;
if (n > 200)
return -1;
if (m > 2e4)
return -2;
if (Q > 5e4)
return -3;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
t[i][j] = 1e18;
}
}
for (int i = 0; i < n; i++)
t[i][i] = 0;
for (int i = 0; i < n; i++)
{
cin >> sj[i];
if (sj[i] > 1e9)
return -4;
if (i!=0&&sj[i] < sj[i - 1])
return -5;
}
for (int i = 0; i < m; i++)
{
long long int qd, zd, qz;
cin >> qd >> zd >> qz;
t[qd][zd] = t[zd][qd] = min(t[qd][zd], qz);
if (qd > n || zd > n)
return -6;
if (qz > 1e9)
return -7;
}
for (int i = 0; i < Q; i++)
{
long long int qd, zd, tz;
cin >> qd >> zd >> tz;
if (qd > n || zd > n)
return -8;
if (tz > 1e9)
return -9;
while (sj[up] <= tz && up < n) {
floy(up);
up++;
}
if (sj[qd] <= tz && sj[zd] <= tz)
{
if (t[qd][zd] == -1||t[qd][zd]==1e18)cout << -1 << endl;
else
{
cout << t[qd][zd] << endl;
}
}
else
{
cout << -1 << endl;
}
}
return 0;
}
J
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
struct lb {
long long int next;
long long int top;
long long int v;
}qxx[10000000];
struct qz
{
long long int qz;
long long int d;
bool operator<(const struct qz& x)const {
return qz > x.qz;
}
};
priority_queue<qz>dl;
long long int m, q, lbys,z,s;
unordered_map<long long int, long long int>bt;
unordered_map<long long int, long long int>vis;
unordered_map<long long int, long long int>hx;
void lj(long long int qd, long long int zd, long long int qz)
{
qxx[++lbys].next = bt[qd];
qxx[lbys].top = zd;
qxx[lbys].v = qz;
bt[qd] = lbys;
}
int main() {
//freopen("20.in", " r ", stdin);
//freopen("20.out", " w ", stdout);
cin >> m >> q>>z>>s;
if(m>2e5||m<1)
return -1;
if(q>1e18||q<1)
return -1;
if(z>1e18||z<1)
return -1;
if(s>1e5||s<1)
return -1;
vis[q] = 0;
vis[z] = 1e18;
for (long long int i = 0; i < m; i++)
{
long long int qd, zd, qz,w;
cin >> qd >> zd >> qz>>w;
if(qd>1e18||qd<1)
return -1;
if(zd>1e18||zd<1)
return -1;
if(qz>1e5||qz<1)
return -1;
if(w>2||w<1)
return -1;
lj(qd, zd, qz);
if (w == 2) {
lj(zd, qd, qz);
}
if (vis[qd] == 0 && qd != q)
{
vis[qd] = 1e18;
}
if (vis[zd] == 0 && zd != q)
{
vis[zd] = 1e18;
}
}
dl.push(qz{ 0,q });
while (dl.size() != 0)
{
struct qz dz = dl.top(); dl.pop();
if (hx.find(dz.d) != hx.end())continue;
hx[dz.d] = 1;
for (long long int i = bt[dz.d]; i != 0; i = qxx[i].next)
{
if (vis[qxx[i].top] > vis[dz.d] + qxx[i].v)
{
vis[qxx[i].top] = vis[dz.d] + qxx[i].v;
if (hx.find(qxx[i].top) == hx.end())
dl.push(qz{ vis[qxx[i].top],qxx[i].top });
}
}
}
if (vis[z] == 1e18)
{
cout << -1;
}
else
{
cout << (long long int)ceil((double)vis[z] / (double)s)<<endl;
//cout <<vis[z]<<" "<<s;
}
return 0;
}
