equation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
You are given two integers N,C and two integer sequences a and b of length N. The sequences are indexed from 1 to N.
Please solve the following equation for x:
∑i=1N|ai⋅x+bi|=C, where |v| means the absolute value of v.
InputThe first line contains an integer T indicating there are T tests. Each test consists of N+1 lines. The first line contains two integers N,C. The i-th line of following Nlines consists of two integers ai,bi.
* 1≤T≤50
* 1≤N≤105
* 1≤ai≤1000
* −1000≤bi≤1000
* 1≤C≤109
* only 5 tests with N larger than 1000
OutputFor each test, output one line.
If there are an infinite number of solutions, this line consists only one integer −1.
Otherwise, this line first comes with an integer m indicating the number of solutions, then you must print m fractions from the smallest to the largest indicating all possible answers. (It can be proved that all solutions can be written as fractions). The fraction should be in the form of "a/b" where a must be an integer, b must be a positive integer, and gcd(abs(a),b)=1. If the answer is 0, you should output "0/1".
Sample Input
4 2 3 1 2 1 -1 3 3 2 1 2 2 2 3 2 1 3 5 4 -1 3 2 1 -1 1 -2 1 -3
Sample Output
-1 2 -3/2 -1/2 0 1 2/1
相当于在数轴上找带权的两点间距离
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps=1e-9;
struct node{
int a,b;
double lo;
bool operator < (const node& y){
return lo<y.lo;
}
};
node z[100100];
ll pa[100100],pb[100100];
ll sa[100100],sb[100100];
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,c;
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++){
scanf("%d%d",&z[i].a,&z[i].b);
z[i].lo=-(double)z[i].b/(double)z[i].a;
}
sort(z+1,z+1+n);
pa[0]=pb[0]=0;
for(int i=1;i<=n+1;i++){
pa[i]=pa[i-1]+z[i].a;
pb[i]=pb[i-1]+z[i].b;
}
sa[n+1]=0,sb[n+1]=0;
for(int i=n;i>=1;i--){
sa[i]=sa[i+1]+z[i].a;
sb[i]=sb[i+1]+z[i].b;
}
vector<ll> v,vv;
int fg=1;
double res=(double)(c+sb[1]);
if(sa[1]!=0){
res/=-(double)sa[1];
}
else{
fg=-1;
}
if(res<z[1].lo+eps){
v.push_back(-sa[1]);vv.push_back(-sb[1]);
}
for(int i=1;i<n;i++){
ll mm=-sa[i+1]+pa[i];
if(mm==0){
if(c+sb[i+1]-pb[i]==0) fg=-1;
}
else{
double res=(double)(c+sb[i+1]-pb[i])/mm;
if(res>z[i].lo+eps && res<z[i+1].lo+eps){
if(fabs(res-z[i].lo)<eps) continue;
v.push_back(mm),vv.push_back(pb[i]-sb[i+1]);
}
}
}
res=(double)(c-pb[n]);
if(pa[n]!=0){
res/=(double)pa[n];
}
else{
fg=-1;
}
if(res>z[n].lo+eps){
v.push_back(pa[n]);vv.push_back(pb[n]);
}
if(fg==-1){
printf("-1\n");
}
else if(v.size()==0){
printf("0\n");
}
else{
printf("%d",(int)v.size());
for(int i=0;i<(int)v.size();i++){
printf(" ");
ll a=v[i],b=vv[i];
b=c-b;
ll g=gcd(abs(a),abs(b));
a/=g,b/=g;
if(a<0){
a*=-1;
b*=-1;
}
printf("%lld/%lld",b,a);
}
printf("\n");
}
}
return 0;
}
permutation 1
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
A sequence of length n is called a permutation if and only if it's composed of the first n positive integers and each number appears exactly once.
Here we define the "difference sequence" of a permutation p1,p2,…,pn as p2−p1,p3−p2,…,pn−pn−1. In other words, the length of the difference sequence is n−1 and the i-th term is pi+1−pi
Now, you are given two integers N,K. Please find the permutation with length N such that the difference sequence of which is the K-th lexicographically smallest among all difference sequences of all permutations of length N.
InputThe first line contains one integer T indicating that there are T tests.
Each test consists of two integers N,K in a single line.
* 1≤T≤40
* 2≤N≤20
* 1≤K≤min(104,N!)
OutputFor each test, please output N integers in a single line. Those N integers represent a permutation of 1 to N, and its difference sequence is the K-th lexicographically smallest.
Sample Input
7 3 1 3 2 3 3 3 4 3 5 3 6 20 10000
Sample Output
3 1 2 3 2 1 2 1 3 2 3 1 1 2 3 1 3 2 20 1 2 3 4 5 6 7 8 9 10 11 13 19 18 14 16 15 17 12
直接暴力枚举所有排列就好了，至多枚举8项，对于后面的只有最后八位是会变的，前面都不变
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
int n,k,ans[22];
struct node{
int a[22];
ll id=0;
}p[maxn];
int cmp(node a,node b){
return a.id<b.id;
}
void solve(){
scanf("%d%d",&n,&k);
rep(i,1,n) ans[i]=i;
if(n>=10){
ans[1]=n;ans[2]=1;
rep(i,3,n) ans[i]=i-1;
rep(i,2,k) next_permutation(ans+3,ans+1+n);
rep(i,1,n) printf(i==n?"%d\n":"%d ",ans[i]);
}
else{
int tmp[22],pos=0;
rep(i,1,n) tmp[i]=i;
do{
pos++;p[pos].id=0;
rep(i,1,n){
p[pos].a[i]=tmp[i];
if(i>1) p[pos].id+=(ll)pow(10,n-i)*(tmp[i]-tmp[i-1]);
}
}while(next_permutation(tmp+1,tmp+1+n));
sort(p+1,p+1+pos,cmp);
rep(i,1,n) printf(i==n?"%d\n":"%d ",p[k].a[i]);
}
}
int main(){
int T;cin>>T;
while(T--) solve();
}
string matching
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
String matching is a common type of problem in computer science. One string matching problem is as following:
Given a string s[0…len−1], please calculate the length of the longest common prefix of s[i…len−1] and s[0…len−1] for each i>0.
I believe everyone can do it by brute force.
The pseudo code of the brute force approach is as the following:
We are wondering, for any given string, what is the number of compare operations invoked if we use the above algorithm. Please tell us the answer before we attempt to run this algorithm.
InputThe first line contains an integer T, denoting the number of test cases.
Each test case contains one string in a line consisting of printable ASCII characters except space.
* 1≤T≤30
* string length ≤106 for every string
OutputFor each test, print an integer in one line indicating the number of compare operations invoked if we run the algorithm in the statement against the input string.
Sample Input
3 _Happy_New_Year_ ywwyww zjczzzjczjczzzjc
Sample Output
17 7 32
签到题，Z-function板子题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+50;
int n;
ll z[maxn];
char S[maxn];
void zjz()
{
z[0]=n;
int j=1,k;
for (int i=1;i<n;i=k)
{
if (j<i) j=i;
while (j<n&&S[j]==S[j-i]) j++;
z[i]=1ll*j-1ll*i;
k=i+1;
while (k+z[k-i]<j)
{
z[k]=z[k-i];k++;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
scanf("%s",S);
n=strlen(S);
zjz();
ll ans=0;
for(int i=1;i<n;i++){
ans+=1ll*z[i];
if(i+z[i]!=n){
ans++;
}
}
printf("%lld\n",ans);
}
return 0;
}
permutation 2
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
You are given three positive integers N,x,y.
Please calculate how many permutations of 1∼N satisfies the following conditions (We denote the i-th number of a permutation by pi):
1. p1=x
2. pN=y
3. for all 1≤i<N, |pi−pi+1|≤2
InputThe first line contains one integer T denoting the number of tests.
For each test, there is one line containing three integers N,x,y.
* 1≤T≤5000
* 2≤N≤105
* 1≤x<y≤N
OutputFor each test, output one integer in a single line indicating the answer modulo 998244353.
Sample Input
3 4 1 4 4 2 4 100000 514 51144
Sample Output
2 1 253604680
签到题，f[i]=f[i-1]+f[i-3],矩阵快速幂
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll md=998244353;
struct matrix{
int a[3][3];
void init(){
memset(a,0,sizeof(a));
}
matrix operator * (matrix& b){
matrix ret;
ret.init();
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
ret.a[i][j]=(1ll*ret.a[i][j]+1ll*a[i][k]*b.a[k][j])%md;
}
}
}
return ret;
}
};
matrix qp(matrix bs,int n){
matrix tmp;
tmp.init();
tmp.a[0][0]=1;tmp.a[0][2]=1;
tmp.a[1][0]=1;tmp.a[2][1]=1;
while(n){
if(n&1) bs=tmp*bs;
tmp=tmp*tmp;
n>>=1;
}
return bs;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,x,y;
scanf("%d%d%d",&n,&x,&y);
if(n==3 || n==2 || n==1){
printf("1\n");
continue;
}
if(x>y) swap(x,y);
int cnt=y-x;
if(x!=1) cnt--;
if(y!=n) cnt--;
matrix bs;
if(cnt<0){
printf("0\n");
continue;
}
else if(cnt<=2){
printf("1\n");
continue;
}
bs.init();
bs.a[0][0]=bs.a[1][0]=bs.a[2][0]=1;
matrix res;
res.init();
res=qp(bs,cnt-2);
printf("%d\n",res.a[0][0]);
}
return 0;
}
