NWRRC 2020题解

本场签到巨多，没写说明就是签到
A

#include 
#include 

B

#include 

using ll = long long;
int main() {
	int a, x, b, y, t;
	std::cin >> a >> x >> b >> y >> t;
	ll ans = 0;
	std::cout << a+21ll*x*(std::max(0, t-30)) << std::endl << b+21ll*y*std::max(0, t-45);


	return 0;
}

C
交互，没写，应该是签到
D

#include
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
typedef pair pir;
string sstr[]={"NOn","YESn"};
const int N=110;
int T,n,w,h,s;
char c[35][35];
char ch;
signed main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);
	cin>>n>>w>>h>>s;
	int mx=0;
	char mxpos;
	for(int i=1;i<=n;i++){
		cin>>ch;
		for(int j=1;j<=h;j++)
			for(int k=1;k<=w;k++){
				cin>>c[j][k];
			}
		for(int j=1;j<=h;j++){
			int tmp=0;
			char pre='.';
			for(int k=1;k<=w;k++){
				if(c[j][k]!=pre){
					tmp++;
					pre=c[j][k];
				}
			}
			if(pre=='#') tmp++;
			if(tmp>mx){
				mx=tmp;
				mxpos=ch;
			}
		}
	}
	int tot=(s-1)/mx+1;
	for(int i=0;i 
E
 一个比较麻烦的欧拉路题。首先对于1边组成的图，需要判断是否可能：
 case1：所有点中，有且只能有1个点入度-出度为-1(且一定要为起点)，有且只能有1个点入度-出度为1
 case2：所有点入度-出度=0
 不需要额外判连通，后面欧拉回路会判断的。
 然后进行dfs求欧拉路，注意当前弧优化。
 然后输出方案，需要特判当前数字只可能为
    
     
      
       
        c
       
      
      
       c
      
     
    c，并且有不可行边的起点为
    
     
      
       
        c
       
      
      
       c
      
     
    c的情形，是不符合题意的。
 
#pragma GCC optimize(3)
#include 
#include 
#include 
 
F
 
#include
#include

#define maxn 3003
#define eps 1e-8
#define zps 1e-4

#define lint int64_t

using
		namespace
					std;

int n;
double P;
lint a[maxn];
lint d[maxn];
lint s[maxn];
lint s2[maxn];
int kotae_pos,kotae_neg;

double dabs(double x){
	
	return x<0.?-x:x;
}

void check(int l,int r){
	
	lint ds=s[r]-s[l-1];
	lint ds2=s2[r]-s2[l-1];
	lint len=r-l+1;
	
	lint nu=ds*ds;
	lint de=ds2*len-ds*ds;
	
	if(de==0){
		
		if(ds>0){
			
			kotae_pos++;
		}
		if(ds<0){
			
			kotae_neg++;
		}
	}
	else{
		
		if(nu>=de*P*P){
			
			if(ds>0){
				
				kotae_pos++;
			}
			if(ds<0){
				
				kotae_neg++;
			}
		}
	}
}

signed main(){
	
	cin>>n>>P;
	
	P-=eps;
	
	for(int i=1;i<=n;i++){
		
		cin>>a[i];
		
		d[i]=a[i]-a[i-1];
		s[i]=s[i-1]+d[i];
		s2[i]=s2[i-1]+d[i]*d[i]; 
	}
	
	for(int i=2;i<=n;i++){
		
		for(int j=i+1;j<=n;j++){
			
			check(i,j);
		}
	}
	
//	for(int i=2;i<=n;i++){
//		
//		if(a[i]>a[i-1]){
//			kotae_pos++;
//		}
//		if(a[i]
//			kotae_neg++;
//		}
//	}
	
	cout< 
G
 整体思路较为简单，就是一个BFS，相较于floyd，其多出了顺序性，因此不能用简单的循环，还需要额外枚举边上的字符即可。
 比赛的时候C语言写的一直WA，结果似乎是因为溢出
 
import java.util.*;
import java.io.*;
import java.math.BigInteger;

class Node {
	
	public Integer u;
	public Integer v;
	public Integer x;
	public BigInteger len;
	
	Node(Integer u_,Integer v_,Integer x_,BigInteger len_){
		
		u = u_;
		v = v_;
		x = x_;
		len = len_;
	}
}

public class Main {
	
	public static Integer trans(char c) {
		
		if(c >= 'A' & c <= 'Z') {
			
			return c - 'A';
		}
		else if(c >= 'a' & c <= 'z') {
			
			return c - 'a';
		}
		
		return -1;
	}
	
	static Integer p = 0, n = 0, m = 0, s = 0, t = 0;
	
	static Boolean big[][][] = new Boolean[30][30][30];
	static Boolean small[][] = new Boolean[30][30];
	static BigInteger edge[][][] = new BigInteger[30][30][30];
	
	static Queue q = new LinkedList();
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		
		for(int i = 0;i < 30;i+=1)
			for(int j = 0;j < 30;j+=1) {
				small[i][j] = false;
				for(int k = 0;k < 30;k+=1) {
					
					big[i][j][k] = false;
					edge[i][j][k] = BigInteger.ZERO;
				}
			}
				
		
		p = in.nextInt();
		
		for(Integer i = 1;i <= p;i+=1) {
			
			String s = in.next();
			String t = in.next();
			t = in.next();
			//System.out.println(s);
			//System.out.println(t);
			
			if(t.length() == 1) {
				
				small[trans(s.charAt(0))][trans(t.charAt(0))]=true;
			}
			else if(t.length() == 2) {
				
				big[trans(s.charAt(0))][trans(t.charAt(0))][trans(t.charAt(1))]=true;
			}
		}
		
		n = in.nextInt();
		m = in.nextInt();
		s = in.nextInt();
		t = in.nextInt();
		
		for(int i = 1;i <= m;i+=1) {
			
			int u,v;
			char x;
			
			u = in.nextInt();
			v = in.nextInt();
			x = in.next().charAt(0);
			
			for(int j = 0;j < 26;j+=1) {
				
				if(small[j][trans(x)]) {
					
					edge[u][v][j] = BigInteger.ONE;
					q.add(new Node(u,v,j,BigInteger.ONE));
				}
			}
		}
		
		while(!q.isEmpty()) {
			
			//System.out.println(q.size());
			
			Node tem = q.element();
			q.remove();
			
			int i = tem.u;
			int k = tem.v;
			int ci = tem.x;
			
			for(int cn = 0;cn < 26;cn+=1) {
				
				for(int cj = 0;cj < 26;cj+=1) {
					
					if(!big[cn][ci][cj]) continue;
					
					for(int j = 1;j <= n;j+=1) {
						
						if(edge[i][k][ci].compareTo(BigInteger.ZERO) == 1 & edge[k][j][cj].compareTo(BigInteger.ZERO) == 1) {
							
							BigInteger nxt = edge[i][k][ci].add(edge[k][j][cj]);
							if(edge[i][j][cn].compareTo(nxt) == 1 | edge[i][j][cn].equals(BigInteger.ZERO)) {
								
								edge[i][j][cn] = nxt;
								q.add(new Node(i,j,cn,edge[i][j][cn]));
							}
						}
					}
				}
			}
			
			for(int cn = 0;cn < 26;cn+=1) {
				
				for(int cj = 0;cj < 26;cj+=1) {
					
					if(!big[cn][cj][ci]) continue;
					
					for(int j = 1;j <= n;j+=1) {
						
						if(edge[j][i][cj].compareTo(BigInteger.ZERO) == 1 & edge[i][k][ci].compareTo(BigInteger.ZERO) == 1) {
							
							BigInteger nxt = edge[j][i][cj].add(edge[i][k][ci]);
							if(edge[j][k][cn].compareTo(nxt) == 1 | edge[j][k][cn].equals(BigInteger.ZERO)) {
								
								edge[j][k][cn] = nxt;
								q.add(new Node(j,k,cn,edge[j][k][cn]));
							}
						}
					}
				}
			}
		}
		
		BigInteger kotae = edge[s][t]['S'-'A'];
		
		if(kotae.equals(BigInteger.ZERO)){
			
			System.out.println("NO");
		}
		else {
			
			System.out.println(kotae);
		}
	}

}

 
H
 下次一定
 I
 
#include


using
		namespace
					std;

int s;

signed main(){
	
	cin>>s;
	
	for(int i=0;i<=1000;i++){
		
		for(int j=0;j<=1000;j++){
			
			if(i*i+j*j==s){
				
				printf("%d %dn",0,0);
				printf("%d %dn",i,j);
				printf("%d %dn",-j,i);
				printf("%d %dn",i-j,i+j);
				goto end;
			}
		}
	}
	
	printf("Impossiblen");
	
end:
	return EOF+1;
}

 
J,K
 HOJ没写SPJ，本身也不太可写
 L
 签到交互。
 M
 
#include
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
typedef pair pir;
string sstr[]={"NOn","YESn"};
const int N=200010;
int T,n,m;
int a[N];
int mi=0,mx=inf;
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		mi=max(mi,a[i]-a[i-1]);
	}
	for(int i=2;i<=n;i++){
		mx=min(mx,a[i]-a[i-2]-1);
	}
	if(mx>=mi){
		cout< 
N
 如果黑色数量恰好有
    
     
      
       
        k
       
       
        /
       
       
        2
       
      
      
       k/2
      
     
    k/2个，那么需要用到两根，数量*2.
 否则，只需要1根即可。
 注意有黑色的范围，如果
    
     
      
       
        k
       
       
        >
       
       
        n
       
      
      
       k>n
      
     
    k>n，则不需要用到黑色较小的木棒，转化为针对白色的方案数进行统计即可。
 注意需要统计出对称和不对称的数量，并对不对称的数量/2才是本质不同的木棒数量。
 
#include
using namespace std;
typedef long long ll;
#define lint ll
#define int ll
lint C(lint a,lint b){
	
	if(a<0||b<0||b>a) return 0;
	if(b>a-b) b=a-b;
	
	lint ans=1;
	
	for(int i=1;i<=b;i++){
		
		ans*=(a-i+1);
		ans/=i;
	}
	
	return ans;
}

signed main()
{
	int n,k;
	int ans=0;
	cin>>n>>k;
	if(k>n) k=2*n-k;
	for(int i=0;i<=k;i++){//有i个黑色
		int tot=C(n,i);//总共的方案数
		int dc=0;//对称的方案数
		if(i%2==0||n%2==1) dc=C(n/2,i/2);
		int ndc=tot-dc;//不对称的方案数
		if(2*i!=k) ans+=dc+ndc/2;
		else ans+=tot+dc;//对称的需要额外一个
	}
	cout<