은 천 선발 전 보충 문제.
A
B, pc 게임 wuwu 이 문 제 는 매우 생각 나 는 2 점 입 니 다.
검색 횟수 가 많아 지면 서 서랍 이 합 법 적 으로 내 려 놓 을 수 있 는 인형 이 점점 줄 어 들 고 있 음 을 알 수 있다.그래서 2 분 의 답 을 고려 하여 가장 먼저 어느 위치 에서 합 법 적 으로 내 려 놓 은 인형 이 k 보다 작 았 는 지 알 아 보 세 요.(인형 을 넣 을 때 이웃 해 서 는 안 된다 는 것 을 주의해 야 한다)
코드 는 다음 과 같 습 니 다.
#include
'
using namespace std;
const int maxn=2e5+7;
int a[maxn];
int tp[maxn];
int main(){
// FAST;
int n,k,L,m;
scanf("%d%d%d%d",&n,&k,&L,&m);
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);
}
int temp1=n;
int temp2=0;
if(temp1>=L){
temp1-=L;
temp2++;
}
temp2+=temp1/(L+1);
if(temp2<k){
cout<<0<<endl;
return 0;
}
//
int l=1;
int r=m;
int temp=-1;
while(l<=r){
int mid=(l+r)>>1;
tp[0]=0;
for(int i=1;i<=mid;i++){
tp[i]=a[i];
}
tp[mid+1]=n+1;
sort(tp,tp+mid+2);
int putin=0;
for(int i=1;i<=mid+1;i++){
int nn=tp[i-1];
int nexx=tp[i];
int d=nexx-nn-1;
if(d>=L){
d-=L;
putin++;
putin+=d/(L+1);
}
}
if(putin<k){
temp=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
cout<<temp<<endl;
}
C pc 선물 사기
이것 은 dp 입 니 다. 방안 수 를 계산 하 는 dp (이전에 비슷 한 것 을 쓴 적 이 있 습 니 다. 그것 은 1 차원 에 불과 합 니 다.) 방안 에 따라 경로 가 다 르 고 / 선물 을 휴대 하 는 것 이 다 르 기 때문에 dp 배열 은 도착 한 특정한 번호 와 현재 선물 가 치 를 기록 합 니 다.(제 시 된 단 방향 변 은 모두 작은 노드 가 큰 노드 를 가리 키 기 때문에 노드 번호 dp 를 누 르 면 됩 니 다. 그렇지 않 으 면 토폴로지 순서 도 있어 야 합 니 다)
생각해 보면 현재 의 총 가치 와 현재 있 는 노드 만 기록 하면 방안 수 를 확정 할 수 있다.
코드 구현:
#include
'
using namespace std;
// dp
const int maxn=2e3+7;
const int mod=998244353;
vector<int> mp[maxn];
ll dp[maxn][maxn];
ll w[maxn];
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>w[i];
}
while(m--){
int a,b;
cin>>a>>b;
//a->b
//
mp[b].pb(a);
}
dp[1][0]=1;
dp[1][w[1]]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<mp[i].size();j++){
int t=mp[i][j];
for(int x=0;x<=k;x++){
dp[i][x]=(dp[i][x]+dp[t][x])%mod;
if(x-w[i]>=0){
dp[i][x]=(dp[i][x]+dp[t][x-w[i]])%mod;
}
}
}
}
ll ans=0;
for(int i=0;i<=k;i++){
ans=(ans+dp[n][i])%mod;
}
cout<<ans<<endl;
}
D. sb 사고 문 제 는 패 리 티 를 직접 판단 하고 코드 를 넣 지 않 습 니 다.
E median 경기 때 이 "배열" 의 뜻 을 못 알 아 봤 어 요.
하나의 v 가 중위 수의 배열 을 형성 하려 면 배열 에서 v 보다 크 고 v 보다 작은 수량 이 같 아야 하기 때문이다.
배열 에서 v 의 위 치 를 직접 찾 습 니 다. v 이전의 모든 배열 에 v 보다 얼마나 큰 것 이 있 는 지, v 보다 얼마나 작은 것 이 있 는 지, 각 점 에서 v 로 형 성 된 배열 이 v 보다 크 고 v 보다 작은 개수 의 차 이 를 기록 한 다음 에 이 차이 가 발생 하 는 횟수 를 기록 합 니 다. (앞 뒤 에 각각 0, 0) v 이후 의 배열 이 똑 같이 처리 되 는 것 을 잊 지 마 세 요.
그리고 앞 뒤로 조합 하면 돼 요.
코드 구현:
#include
'
using namespace std;
const int maxn=1e5+7;
int a[maxn];
map<int,ll> mp1,mp2;//
int main(){
int n,v;
scanf("%d%d",&n,&v);
int i0=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==v){
i0=i;
}
}
int cntb=0;
int cnts=0;
mp1[0]++;
mp2[0]++;
for(int i=i0-1;i>=1;i--){
if(a[i]<v){
cnts++;
}
else{
cntb++;
}
mp1[cnts-cntb]++;
}
cntb=0;
cnts=0;
for(int i=i0+1;i<=n;i++){
if(a[i]<v){
cnts++;
}
else{
cntb++;
}
mp2[cnts-cntb]++;
}
ll ans=0;
for(int i=0;i<=n;i++){
//cout<
ans+=mp1[-i]*mp2[i];
if(i!=0)
ans+=mp1[i]*mp2[-i];
}
printf("%lld
",ans);
}
F 재 구축 네트워크
이 문 제 는 매우 재미 있어 서 선배 와 토론 하기 시 작 했 을 때 이것 이 가짜 문제 인 줄 알 았 는데 나중에 문제 풀이 의 해석 을 보고 나 서 야 이 문제 의 묘 미 를 발견 하 였 다.
아 이 디 어 는 제 시 된 무방 향 그림 을 한 번 달 리 는 데 가장 큰 생 성 트 리 입 니 다. 만약 에 사용 하 는 가장자리 에 k 보다 작은 것 이 있다 면 정 답 sum (k 보다 작고 사용 하 는 가장자리 - k) 입 니 다. 사용 하 는 가장자리 가 k 보다 크다 면 정 답 은 모든 가장자리 와 k 의 가장 작은 차이 입 니 다. (왜 일 까요?)사 고 를 통 해 알 수 있 듯 이 현재 나무 가 형성 되 었 습 니 다. k 차이 가 가장 작은 그 변 이 나무 에 없 으 면 바로 교체 할 수 있 습 니 다. (바 꾼 변 두 노드 (a, b) 임 의 점 과 집합 이 연 결 된 그 변 을 삭제 하면 됩 니 다)
(비주류 최대 생 성 트 리 쓰기... 더미 최적화 prim, 변 권 모두 마이너스)
코드 구현:
#include
'
using namespace std;
const int maxn=1e5+7;
const int maxm=2e5+7;
struct edge{
int to;
ll w;
};
vector<edge> mp[maxn];
typedef pair<ll,int> P;//first ，second
bool vis[maxn];
ll dis[maxn];
int n,m;
ll k;
ll cntedge[maxn];
ll ed[maxm];
int cnt=0;
void prim(){
//
priority_queue<P,vector<P>,greater<P> >q;
q.push({
0,1});// ；
while(q.size()){
P t=q.top();
q.pop();
ll w0=t.first;
ll v0=t.second;
//cout<
if(vis[v0]) continue;
vis[v0]=1;
if(w0!=0)
cntedge[++cnt]=-w0;
for(int i=0;i<mp[v0].size();i++){
edge e=mp[v0][i];
q.push({
e.w,e.to});
}
}
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int a,b;
ll c;
cin>>a>>b>>c;
mp[a].pb({
b,-c});//
mp[b].pb({
a,-c});
ed[i]=c;
}
prim();
ll ans=0;
int flag=0;
ll minn=1e15;
for(int i=1;i<=cnt;i++){
//cout<
if(cntedge[i]<k){
flag=1;
ans+=abs(k-cntedge[i]);
//cout<
}
}
//cout<
if(flag==1){
cout<<ans<<endl;
}
else{
for(int i=1;i<=m;i++){
minn=min(minn,abs(k-ed[i]));
}
cout<<minn<<endl;
}
}
G
H. pc 가 문 제 를 낼 거 예요.
맞 아, 맞 아.우 k, 바로 sb 문제 입 니 다.
#include
'
using namespace std;
ll cnt[10000007];
int a[1000007];
bool vis[100000007];
int main(){
int n,k;
scanf("%d%d",&n,&k);
ll ans=0;
for(int i=1;i<=n;i++){
ll temp;
scanf("%lld",&temp);
temp%=k;
//a[i]=k;
cnt[temp]++;
}
for(int i=0;i<k;i++){
if(vis[i]==1) continue;
if(i==0|k-i==i){
//
ans+=cnt[i]*(cnt[i]-1)/2;
vis[i]=1;
}
else{
ans+=cnt[i]*cnt[k-i];
vis[i]=1;
vis[k-i]=i;
}
}
printf("%lld
",ans);
}
int cnt[10000007];
int a[1000007];
int main(){
int n,k;
scanf("%d%d",&n,&k);
ll temp;
ll ans=0;
while(n--){
scanf("%lld",&temp);
temp%=k;
if(temp==0){
ans+=cnt[0];
}
else{
ans+=cnt[k-temp];
}
cnt[temp]++;
}
printf("%lld
",ans);
return 0;
}
(또 하 나 는 모 팀, 하 나 는 dp 를 쓰 지 않 았 습 니 다. 쓰 고 바로 문 제 를 보충 합 니 다)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Zuma 문제 풀이신기한 전송문 제목: 문제풀이: 돌아가는 과정을 고려하여 모두 없애는 최소한의 용도로 설정하면 우리는 의심할 여지없이 이 몇 가지 소법이 있다.중간에 공 1개가 있고 그 좌우 양측의 부분을 제거한 후 3부분의 충돌을...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
