- C20250070's blog
个别难题题解
-
C20250070 LV 10 @ 2022-11-16 19:53:56
orz
#include<bits/stdc++.h>
using namespace std;
#define int long long
char u[1001][1001];
int t;
bool good(){
for(int i=0;i<t;i++) if(u[i][i]!='-'){
//cout<<"BAD3\n";
return false;
}
for(int i=0;i<t;i++) for(int j=0;j<t;j++){
if(i==j) continue;
if(u[i][j]==u[j][i]&&u[i][j]!='D'){
return false;
}
if((u[i][j]!='W'&&u[i][j]!='D'&&u[i][j]!='L')||(u[j][i]!='W'&&u[j][i]!='L'&&u[j][i]!='D')){
return false;
}
if((u[i][j]=='D'||u[j][i]=='D')&&u[i][j]!=u[j][i]) return false;
}
return true;
}
signed main(){
scanf("%lld",&t);
for(int i=0;i<t;i++) for(int j=0;j<t;j++) cin>>u[i][j];
if(good()) printf("correct");
else printf("incorrect");
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,c[21];
bool vis[1001];
int dis[1001];
int sx;
void Dijkstra(){
priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > > q;
q.push(make_pair(0,make_pair(1,sx)));
int ans=-1;
while(!q.empty()){
int mk=q.top().first;
int cao=q.top().second.second;
int h=q.top().second.first;
q.pop();
if(vis[h]){
continue;
}
if(h==n){
ans=mk;
break;
}
dis[h]=mk;
vis[h]=true;
//cout<<h<<" "<<mk<<" "<<dis[h]<<endl;
//if(dis[h]==mk) cout<<"TRUE\n";
// else cout<<"FALSE\n";
for(int i=1;i<=m;i++){
int ml=c[i];
if(ml+h>0&&ml+h<=n){
if(!vis[ml+h]){
//cout<<dis[h]+abs(cao-i)+abs(ml)*2<<" "<<h+ml<<" "<<i<<" "<<h<<" "<<endl;
q.push(make_pair(dis[h]+abs(cao-i)+abs(ml)*2,make_pair(h+ml,i)));
}
}
}
}
printf("%lld",ans);
}
signed main(){
scanf("%lld %lld",&n,&m);
for(int i=1;i<=m;i++){
scanf("%lld",&c[i]);
if(c[i]==0) sx=i;
}
Dijkstra();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p[44]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,6486480,147026880,294053760,367567200,698377680,735134400};
signed main(){
int k;
scanf("%lld",&k);
int l=0,r=43,mid=(l+r)/2;
int ans;
while(l<=r){
if(k>=p[mid]){
ans=p[mid];
l=mid+1;
}
else r=mid-1;
mid=(l+r)/2;
}
printf("%lld",ans);
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[501];
int f[501][501];
int main() {
int n;
scanf("%d",&n);
scanf("%s",s+1);
memset(f,0x7F,sizeof(f));
for(int i=1;i<=n;++i)
f[i][i]=1;
for(int l=1;l<n;++l)
for(int i=1,j=1+l;j<=n;++i,++j) {
if(s[i]==s[j])
f[i][j]=min(f[i+1][j],f[i][j-1]);
else
for(int k=i;k<j;++k)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
printf("%d",f[1][n]);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[41];
//b[41];
signed main(){
int t;
scanf("%lld",&t);
while(t--){
int n;
scanf("%lld",&n);
for(int i=1;i<=2*n;i++){
scanf("%lld",&a[i]);
//b[a[i]]=i;
}
int cnt=0;
// for(int i=2;i<=2*n;i+=2){
// if(a[i]/2!=a[i-1]/2){
// int p=a[i-1];
// int q=(p%2==1)?(p-1):(p+1);
// swap(a[i],a[b[q]]);
// swap(b[a[i]],b[a[b[p]]]);
// cnt++;
// }
// }
for(int i=1;i<=2*n;i+=2){
if(a[i]/2!=a[i+1]/2){
for(int j=i+2;j<=2*n;j++){
if(a[j]/2==a[i]/2){
swap(a[j],a[i+1]);
cnt++;
break;
}
}
}
}
printf("%lld\n",cnt);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll C(ll k){
if(k<=1) return 0;
return k*(k-1)/2;
}
int main(){
ll n,m;
scanf("%lld %lld",&n,&m);
ll ans=C(n)+C(m);
printf("%lld",ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool vis[100001];
bool cmp(ll a,ll b){
return a>b;
}
int main(){
ll n;
scanf("%lld",&n);
ll a[50001],b[50001];
for(ll i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
vis[x]=true;
b[i]=x;
}
ll cnt=0;
for(ll i=2*n;i;i--){
if(!vis[i]){
a[++cnt]=i;
}
}
sort(b+1,b+n/2+1,cmp);
ll z1=n/2,z2=n/2;
ll ans=0;
while(true){
while(b[z2]>a[z1]&&z1>0) z1--;
if(z1){
ans++;
z2--;
z1--;
if(z1==0) break;
}
else break;
}
sort(b+n/2+1,b+n+1,cmp);
z1=n/2+1,z2=n/2+1;
while(true){
while(b[z2]<a[z1]&&z1<=n) z1++;
if(z1==n+1) break;
else{
ans++;
z1++;
z2++;
if(z1==n+1) break;
}
}
printf("%lld",ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool vis[100001];
int main(){
ll n;
scanf("%lld",&n);
priority_queue<ll,vector<ll>,greater<ll> > q1,q2;
for(ll i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
vis[x]=true;
q1.push(x);
}
for(ll i=1;i<=2*n;i++){
if(!vis[i]) q2.push(i);
}
ll ans=0;
while(!q1.empty()&&!q2.empty()){
while(!q2.empty()&&q1.top()>=q2.top()){
q2.pop();
}
if(!q1.empty()&&!q2.empty()){
ans++;
q1.pop();
q2.pop();
}
else break;
}
printf("%lld",ans);
}
#include<cstdio>
#include<set>
using namespace std;
const int maxn = 5e4 + 5;
int n, vis[maxn << 1], pre[maxn], suf[maxn], a[maxn], ans;
set <int> se1, se2;
int read(void) {
char c; while (c = getchar(), c < '0' || c > '9'); int x = c - '0';
while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x;
}
int main() {
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read(); vis[a[i]] = 1;
}
for (int i = 1; i <= n * 2; ++ i)
if (!vis[i]) se1.insert(i), se2.insert(-i);
for (int i = 1; i <= n; ++ i) {
set <int>::iterator it = se1.lower_bound(a[i]);
if (it != se1.end()) pre[i] = pre[i - 1] + 1, se1.erase(it);
else pre[i] = pre[i - 1];
}
for (int i = n; i ; -- i) {
set <int>::iterator it = se2.lower_bound(-a[i]);
if (it != se2.end()) suf[i] = suf[i + 1] + 1, se2.erase(it);
else suf[i] = suf[i + 1];
}
for (int i = 0; i <= n; ++ i) ans = max(ans, pre[i] + suf[i + 1]);
printf("%d", ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll a,b,c,d;
scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
ll e=a-c,f=d-b;
if(e==0&&f==0) printf("infinite");
else if(e==0) printf("impossible");
else printf("%lld",f/e);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll x;
scanf("%lld",&x);
ll ans=1;
while(x!=1){
ans++;
if(x%2==0) x/=2;
else x=x*3+1;
}
printf("%lld",ans);
}
#include<bits/stdc++.h>
using namespace std;
#define ll int
int main(){
ll x;
scanf("%d",&x);
ll ans=0;
for(ll i=1;i<=x;i++){
ll day=i+1945;
if((day%4==0&&day%100!=0)||day%400==0) ans++;
ans+=365;
}
if(x>949&&x<=970) ans--;
printf("%d",ans);
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll x[50001],y[50001];
ll ans=0x3f3f3f3f3f3f3f3f;
int main(){
ll l1=-1,l2=-1,u1=-1,u2=-1,d1=-1,d2=-1,r1=-1,r2=-1;
ll n;
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
scanf("%lld %lld",&x[i],&y[i]);
if(u1==-1) u1=y[i];
else if(u1>y[i]){
u2=u1;
u1=y[i];
}
else if(u2>y[i]||u2==-1) u2=y[i];
if(d1==-1) d1=y[i];
else if(d1<y[i]){
d2=d1;
d1=y[i];
}
else if(d2<y[i]||d2==-1) d2=y[i];
if(l1==-1) l1=x[i];
else if(l1>x[i]){
l2=l1;
l1=x[i];
}
else if(l2>x[i]||l2==-1) l2=x[i];
if(r1==-1) r1=x[i];
else if(r1<x[i]){
r2=r1;
r1=x[i];
}
else if(r2<x[i]||r2==-1) r2=x[i];
}
for(ll i=1;i<=n;i++){
ll l,r,u,d;
l=(x[i]==l1?l2:l1);
r=(x[i]==r1?r2:r1);
u=(y[i]==u1?u2:u1);
d=(y[i]==d1?d2:d1);
ans=min(ans,(r-l)*(d-u));
}
printf("%lld",ans);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
ll w,s;
}e[100001];
bool cmp(node a,node b){
return a.w>b.w;
}
ll ans=0;
int main(){
ll n;
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
scanf("%lld %lld",&e[i].w,&e[i].s);
}
sort(e+1,e+n+1,cmp);
ll m=0x3f3f3f3f3f3f3f3f;
for(ll i=1;i<=n;i++){
if(m>=e[i].s){
m=e[i].s;
ans++;
}
}
printf("%lld",ans);
return 0;
}
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int INF=1000000;
struct edge
{
int to;
int w[2];
};
vector<edge> G[500010];
int d1[500010];
int d2[500010];
int n,m;
bool used[500010];
void spfa(int d[],int mode)
{
for (int i=1;i<=n;i++)
{
d[i]=INF;
used[i]=false;
}
queue<int> q;
d[n]=0;
q.push(n);
used[n]=true;
while (!q.empty())
{
int u=q.front();q.pop();
used[u]=false;
for (int i=0;i<G[u].size();i++)
{
edge e=G[u][i];
int v=e.to;
int w=e.w[mode];
if (d[v]>d[u]+w)
{
d[v]=d[u]+w;
if (!used[v])
{
q.push(v);
used[v]=true;
}
}
}
}
}
int main()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int u,v,w1,w2;
cin>>u>>v>>w1>>w2;
edge e;
e.to=u;
e.w[0]=w1;
e.w[1]=w2;
G[v].push_back(e);
}
spfa(d1,0);
spfa(d2,1);
for (int i=1;i<=n;i++)
{
for (int j=0;j<G[i].size();j++)
{
edge e=G[i][j];
int u=i,v=e.to,w1=e.w[0],w2=e.w[1];
int cnt=0;
if (d1[v]!=d1[u]+w1) cnt++;
if (d2[v]!=d2[u]+w2) cnt++;
G[i][j].w[0]=cnt;
}
}
spfa(d1,0);
cout<<d1[1];
return 0;
}